1.9 Логически преобразувания

Нормална дизюнктивна форма и опростяване

Чрез използване на схеми еквивалентности една формула може да бъде преобразувана в друга, различна на външен вид формула, която е логически еквивалентна на първата. Логически еквивалентните формули отговарят на твърдения, които имат един и същ смисъл. Това означава, че в тях обикновено участват едни и същи букви за твърдения, които като се интерпретират по определен начин (всяка буква – с определено конкретно твърдение), се получават две твърдения, казващи по различен начин едно и също нещо. Преобразуването на дадена формула в логически еквивалентна на нея става, като въз основа на определена схема еквивалентност се замества част от формулата с логически еквивалентна на нея част (като граничен случай заместваната формула може да е и цялата формула). Принципът за заменимост на еквивалентните гарантира, че при това заместване се получава формула, която е логически еквивалентна на началната. Така например въз основа на схемата еквивалентност, която в 1.8 Естествена дедукция нарекохме „материална импликация“ („α→β“ ⟺ „¬α∨β“), бихме могли да преобразуваме

(1) [¬p→(q→¬r)] → ¬(q∧r)

в следните три формули: „¬[¬p→(q→¬r)]∨¬(q∧r)“, „[¬¬p∨(q→¬r)]→¬(q∧r)“ или „[¬p→(¬q∨¬r)]→¬(q∧r)“. Първата от тях е получена чрез заместване на (1) като цяло (т.е. самото (1) е логически еквивалентно на първата формула въз основа на тази схема еквивалентност). Втората и третата са получени чрез замяна на части на (1) с логически еквивалентни на тях формули въз основа на същата схема (съответно на „¬p→(q→¬r)“ с „¬¬p∨(q→¬r)“ и на „q→¬r“ с „¬q∨¬r“).

Ако е налице поредица от такива еквивалентни преобразувания, ясно е, че формулата, до която ще стигнем накрая, ще бъде логически еквивалентна на началната, тъй като всяка формула ще e еквивалентна на предишната. Например, тръгвайки от (1), бихме могли последователно да направим следните преобразувания, при всяко от които заместваме някаква импликация с израз, съдържащ дизюнкция и отрицание, въз основа на схемата еквивалентност на материалната импликация:

[¬p→(q→¬r)] → ¬(q∧r)
¬[¬p→(q→¬r)] ∨ ¬(q∧r)
¬[¬¬p∨(q→¬r)] ∨ ¬(q∧r)
¬[¬¬p∨(¬q∨¬r)] ∨ ¬(q∧r)

След това можем да приложим схемата еквивалентност, която (в естествената дедукция) нарекохме „двойно отрицание“ (α ⟺ „¬¬α“), заменяйки „¬¬p“ с „p“:

¬[p∨(¬q∨¬r)] ∨ ¬(q∧r)

Прилагайки схемата еквивалентност, която нарекохме „закон на Де Морган“ („¬(α∨β)“ ⟺ „¬α∧¬β“), и замествайки „¬[p∨(¬q∨¬r)]“ с „¬p∧¬(¬q∨¬r)“, получаваме

[¬p∧¬(¬q∨¬r)] ∨ ¬(q∧r)

Законът на Де Морган може да се приложи още един път върху втория член на конюнкцията в квадратните скоби, като „¬(¬q∨¬r)“ се замени с „¬¬q∧¬¬r“:

[¬p ∧ ¬¬q ∧ ¬¬r] ∨ ¬(q∧r)

В първият член на дизюнкцията участват само конюнкции, поради което не сме сложили скоби около „¬¬q∧¬¬r“. По-нататък въз основа на схемата на двойното отрицание можем да махнем двойките отрицания пред „q“ и „r“ получавайки

[¬p∧q∧r] ∨ ¬(q∧r)

Накрая, прилагайки закона на Де Морган в другата му форма („¬(α∧β)“ ⟺ „¬α∨¬β“), заменяме „¬(q∧r)“ с „¬q∨¬r“ и получаваме

(2) [¬p∧q∧r] ∨ ¬q ∨ ¬r

Скоби около „¬q∨¬r“ не са нужни, защото изразът е дизюнкция, която е свързана с останалата част на целия израз отново с дизюнкция, т.е. целият израз е дизюнкция с три члена. Формулата (2) е логически еквивалентна на началната формула (1) („[¬p→(q→¬r)]→¬(q∧r)“), защото е получена от нея чрез поредица от еквивалентни преобразувания. (2) казва същото, каквото и (1), но за твърдение с формата на (2) е много по-лесно да се види кога би било истинно и кога не. (2) е дизюнкция, която е истинна, ако и само ако поне един от нейните членове е истинен, което е изпълнено само в три случая – когато „q“ и „r“ са истинни, а „p“ е неистинно (тогава e истинно „¬p∧q∧r“), когато „q“ е неистинно (тогава е истинно „¬q“) и когато „r“ е неистинно (тогава е истинно „¬r“).

Изразът в (2) се намира в така наречената „нормална дизюнктивна форма“. Това е дизюнкция от конюнкции на букви за твърдения или отрицания на букви за твърдения. Отдолу е даден един стандартен пример:

(q∧r) ∨ (¬p∧¬q∧r) ∨ (s∧¬r)

Изразът е дизюнкция, която има три члена, всеки от които е конюнкция, като членовете на конюнкциите са или букви за твърдения, или отрицания на букви за твърдения.

Като граничен случай конюнкциите в една нормална дизюнктивна форма може да са така да се каже с един член, т.е. да не са конюнкции, а единични букви за твърдения или отрицания на такива букви. Такива са следните две формули, а също и (2) по-горе:

r ∨ (q∧s) ∨ ¬p
¬r ∨ ¬p

Също като граничен случай дизюнкцията в една нормална дизюнктивна форма може да има така да се каже един член, т.е. да не е дизюнкция от конюнкции (на букви за твърдения или техните отрицания), а да се състои от една единствена такава конюнкция. Такава е например следната формула:

p∧q∧¬r∧w

Всяка формула може да бъде преобразувана в нормална дизюнктивна форма. Това става чрез следните стъпки (прилагани, ако е нужно, повече от един път):

α→β ⟺ ¬α∨β
¬(α→β) ⟺ α∧¬β
α↔β ⟺ (α∧β)∨(¬α∧¬β)
α↔β ⟺ (α→β)∧(β→α)
¬(α∨β) ⟺ ¬α∧¬β
¬(α∧β) ⟺ ¬α∨¬β
¬¬α ⟺ α
α∧(β∨γ) ⟺ (α∧β)∨(α∧γ)

Преди да разгледаме още примери за преобразуване на изрази в нормална дизюнктивна форма нека се разберем отново да използваме конвенцията да не групираме със скоби членовете на конюнкциите или дизюнкциите, когато са повече от два. Това е практика, към която се придържахме при истинностно-функционалния анализ и таблиците за истинност, но която временно изоставихме при естествената дедукция. Съгласно тази конвенция например пишем „p∧q∧r∧s“ вместо „(p∧q)∧(r∧s)“, „p∧[q∧(r∧s)]“, или какъвто и да e друг възможен начин за групиране на членовете на конюнкцията със скоби. По същия начин ще процедираме и с дизюнкциите.

Нека сега сведем до нормална дизюнктивна форма следния доста сложен израз:

¬(¬[¬(p→¬q)→¬(r∧p)]∧{[(q∧s)→p]→q})

По закона на Де Морган, приложен върху формулата като цяло, получаваме:

¬¬[¬(p→¬q)→¬(r∧p)] ∨ ¬{[(q∧s)→p]→q}

Махаме двойното отрицание пред първия член на дизюнкцията:

[¬(p→¬q)→¬(r∧p)] ∨ ¬{[(q∧s)→p]→q}

По втората от схемите еквивалентности за импликацията, приложена върху втория член на дизюнкцията, получаваме:

[¬(p→¬q)→¬(r∧p)] ∨ {[(q∧s)→p]∧¬q}

По първата схема за импликацията, приложена към първия член на дизюнкцията, получаваме:

¬¬(p→¬q) ∨ ¬(r∧p) ∨ {[(q∧s)→p]∧¬q}

Mахаме двойното отрицание пред първия член на дизюнкцията и прилагаме Де Морган към втория ѝ член (на това формално отговарят две стъпки, но неформално ги комбинираме в една):

(p→¬q) ∨ ¬r ∨ ¬p ∨ {[(q∧s)→p]∧¬q}

Разлагаме двете импликации по първата схема за импликацията:

¬p ∨ ¬q ∨ ¬r ∨ ¬p ∨ {[¬(q∧s)∨p]∧¬q}

Прилагаме дистрибутивния закон върху последния член на главната дизюнкция. (Това, че „¬q“ стои от дясната страна на дизюнкцията в квадратните скоби, е без значение – можем да си го представим написано и отляво, тъй като редът на членовете в една конюнкция е без значение.)

¬p ∨ ¬q ∨ ¬r ∨ ¬p ∨ [¬q∧¬(q∧s)] ∨ (¬q∧p)

Освобождаваме се от отрицанието пред скобите в предпоследния член на дизюнкцията по Де Морган:

¬p ∨ ¬q ∨ ¬r ∨ ¬p ∨ [¬q∧(¬q∨¬s)] ∨ (¬q∧p)

Прилагаме дистрибутивния закон върху израза в квадратните скоби:

¬p ∨ ¬q ∨ ¬r ∨ ¬p ∨ (¬q∧¬q) ∨ (¬q∧¬s) ∨ (¬q∧p)

Изразът вече е в нормална дизюнктивна форма. Нека разместим малко членовете на дизюнкцията:

¬p ∨ ¬p ∨ ¬q ∨ (¬q∧¬q) ∨ ¬r ∨ (¬q∧¬s) ∨ (¬q∧p)

Формулата може да бъде опростена, продължавайки да бъде в нормална дизюнктивна форма. Тъй като „¬p“ се повтаря като член на дизюнкцията, можем да махнем едното „¬p“ по схемата еквивалентност, която нарекохме „тавтология“ („α∨α“ ⟺ α). Получаваме

¬p ∨ ¬q ∨ (¬q∧¬q) ∨ ¬r ∨ (¬q∧¬s) ∨ (¬q∧p)

Можем да махнем и едното от двете „¬q“ в „¬q∧¬q“ по другата форма на същата схема еквивалентност („α∧α“ ⟺ α). Получаваме

¬p ∨ ¬q ∨ ¬q ∨ ¬r ∨ (¬q∧¬s) ∨ (¬q∧p)

Сега можем да махнем и едното от двете повтарящи се „¬q“:

¬p ∨ ¬q ∨ ¬r ∨ (¬q∧¬s) ∨ (¬q∧p)

Изразът може да бъде опростен още. За целта ще въведем следната схема еквивалентност, чиято логическа валидност може лесно да бъде проверена чрез истинностно-функционален анализ или таблица за истинност:

α∨(α∧β) ⟺ α

Ако преподредим членовете на дизюнкцията по следния начин

¬p ∨ ¬q ∨ (¬q∧¬s) ∨ (¬q∧p) ∨ ¬r

става очевидно, че въз основа на въведената схема еквивалентност изразът „¬q ∨ (¬q∧¬s)“ може да бъде заменен с „¬q“, т.е. реално десният член на дизюнкцията („¬q∧¬s“) може да бъде съкратен:

¬p ∨ ¬q ∨ (¬q∧p) ∨ ¬r

По същата причина може да се съкрати и „¬q∧p“:

¬p ∨ ¬q ∨ ¬r

Сега вече нормалната дизюнктивна форма е максимално опростена. Получава се, че началната сложна формула не е казвала нищо по-различно от това, че поне едно от твърденията p, q или r не е истинно.

Ако нормална дизюнктивна форма, до която сме стигнали, е по-сложна, е добре буквите в конюнкциите да се подредят по азбучен ред. По този начин се вижда по-лесно дали има повтарящи се изрази, което може да доведе до опростяване. Така например, ако сме стигнали до формулата

(q∧p∧¬s) ∨ (p∧q) ∨ (p∧¬s∧q)

като подредим членовете на конюнкциите в нея по азбучен ред, ще получим израза

(p∧q∧¬s) ∨ (p∧q) ∨ (p∧q∧¬s)

от който ясно се вижда, че първият и последният член на дизюнкцията са еднакви и следователно единият от тях може да се съкрати:

(p∧q∧¬s) ∨ (p∧q)

Освен това се вижда, че вторият член на дизюнкцията („p∧q“) е част от първия ѝ член, и следователно първият член може да се съкрати въз основа на схемата „α∨(α∧β)“ ⟺ α, така че изразът в крайна сметка се свежда до „p∧q“.

В по-предишния пример първо преобразувахме началния сложен израз до нормална дизюнктивна форма и след това го опростихме. Опростяванията обаче могат да се правят и по време на самия процес на свеждане до нормална дизюнктивна форма. Това всъщност е препоръчително, защото по този начин свеждането до нормална дизюнктивна форма се опростява много. В примера опростяване можеше да се направи още в момента, когато стигнахме до израза

¬p ∨ ¬q ∨ ¬r ∨ ¬p ∨ {[¬(q∧s)∨p]∧¬q}

Тук целият последен сложен член на дизюнкцията може да се съкрати въз основа на схемата „α∨(α∧β)“ ⟺ α, тъй като той е конюнкция между „¬q“ и някакъв друг израз, а „¬q“ участва още като член на главната дизюнкция („¬q“ изпълнява ролята на α в схемата, а „¬(q∧s)∨p“ – на β).

Следва списък на схемите еквивалентности, които можем да използваме за опростяване. Групирани са по двойки и логическата им валидност лесно може да се провери с истинностно-функционален анализ или с таблици за истинност.

i a) α ∨ α ⟺ α
b) α ∧ α ⟺ α

ii a) α ∨ (α∧β) ⟺ α
b) α ∧ (α∨β) ⟺ α

iii a) α ∨ (β∧¬β) ⟺ α (а също и α ∨ (β∧¬β∧γ) ⟺ α)
b) α ∧ (β∨¬β) ⟺ α (а също и α ∧ (β∨¬β∨γ) ⟺ α)

iv a) α ∨ (¬α∧β) ⟺ α ∨ β
b) α ∧ (¬α∨β) ⟺ α ∧ β

iii a) ни дава възможност да съкращаваме противоречия от вида „β∧¬β“ или съдържащи такива противоречия конюнкции, когато са членове на дизюнкции, а iii b) – да съкращаваме тавтологии от вида „β∨¬β“ или съдържащи такива тавтологии дизюнкции, когато са членове на конюнкции. Например въз основа на iii a) можем да съкратим втория, третия и последния член на следната дизюнкция:

(p∧q∧r) ∨ (q∧¬q∧r) ∨ (¬p∧q∧p∧r) ∨ (q∧r∧¬s) ∨ (r∧¬r)

Въз основа на iv a) пък например във формулата

(p∧r) ∨ [¬(p∧r)∧q]

бихме могли да съкратим израза „¬(p∧r)“ заедно със знакът за конюнкция, който го свързва с „q“, получавайки

(p∧r) ∨ q

По аналогичен начин въз основа на iv b) например в „p∧r∧[¬(p∧r)∨q]“ можем да съкратим „¬(p∧r)“ заедно с дизюнкцията, която свързва този израз с „q“, получавайки „p∧r∧q“.

Същите опростявания могат да се правят и при изрази от вида „¬α∨(α∧β)“ и „¬α∧(α∨β)“, в които отрицанието стои пред външния за скобите, а не пред вътрешния от двата повтарящи се изрази. Резултатите от опростяванията са съответно „¬α∨β“ и „¬α∧β“, като основанията за опростяванията са отново схемите в iv, но с едно допълнително прилагане на двойно отрицание, защото „¬α∨(α∧β)“ и „¬α∧(α∨β)“ по двойно отрицание са логически еквивалентни съответно на „¬α∨(¬¬α∧β)“ и „¬α∧(¬¬α∨β)“, които въз основа на схемите в iv са еквивалентни съответно на „¬α∨β“ и „¬α∧β“.

Като следващ пример нека сведем до нормална дизюнктивна форма и същевременно опростим израза „{¬[r∨¬(s→p)]∧(s→¬p)}→(r∧s)“:

¬{¬[r∨¬(s→p)]∧(s→¬p)} ∨ (r∧s) по материална импликация
¬¬[r∨¬(s→p)] ∨ ¬(s→¬p) ∨ (r∧s) по Де Морган
r ∨ ¬(s→p) ∨ ¬(s→¬p) ∨ (r∧s) по двойно отрицание

Тук можем да съкратим „r∧s“, тъй като съгласно ii a) „r∨(r∧s)“ е еквивалентно на „r“ (редът на членовете на дизюнкцията е без значение – можем да си ги представим разместени така, че „r“ и „r∧s“ стоят едно до друго):

r ∨ ¬(s→p) ∨ ¬(s→¬p) по ii a)
r ∨ (s∧¬p) ∨ (s∧¬¬p) по материална импликацията, два пъти
r ∨ (s∧¬p) ∨ (s∧p) по двойно отрицание

Формулата вече е в нормална дизюнктивна форма и е значително по-проста от началния израз, но може да бъде опростена още, ако приложим дистрибутивния закон в обратната посока на тази, в която обикновено го прилагаме:

r ∨ [s ∧(¬p∨p)] по дистрибуция

Сега можем съкратим „¬p∨p“ въз основа на iii b):

r ∨ s по iii b)

Две от използваните в логическите преобразувания схеми еквивалентности – законът на Де Морган и дистрибутивният закон – важат също за конюнкции и дизюнкции с повече от два члена. Досега законът на Де Морган беше използван само в следните му две форми:

¬(α∨β) ⟺ ¬α∧¬β
¬(α∧β) ⟺ ¬α∨¬β

Те обаче могат да се разглеждат като частни случаи на закона, тъй като той е валиден за конюнкции и дизюнкции с произволен брой членове:

¬(α∨β∨γ...) ⟺ ¬α∧¬β∧¬γ...
¬(α∧β∧γ...) ⟺ ¬α∨¬β∨¬γ...

Това, че тези схеми еквивалентности са логически валидни, се вижда от условията за истинност на дизюнкцията и конюнкцията. Независимо колко члена има, всяка дизюнкция е истинна, ако и само ако поне един от членовете й е истинен. Значи отрицанието ѝ ще е истинно, ако и само ако нито един от членовете ѝ не е истинен. От своя страна конюнкцията е истинна, ако и само ако всеки от членовете ѝ е истинен. Значи отрицанието ѝ ще е истинно, ако и само ако поне един от членовете ѝ е неистинен.

Досега дистрибутивният закон беше използван в една от следните му две форми:

α∧(β∨γ) ⟺ (α∧β)∨(α∧γ)
α∨(β∧γ) ⟺ (α∨β)∧(α∨γ)

Ако в „(α∨β)∧(γ∨δ)“ въз основа на първата схема еквивалентност разпределим „α∨β“ в дизюнкцията „γ∨δ“, ще получим

[(α∨β)∧γ] ∨ [(α∨β)∧δ]

Сега, ако отново приложим същата форма на дистрибутивния закон върху изразите в двете двойки квадратни скоби, ще получим:

(α∧γ) ∨ (β∧γ) ∨ (α∧δ) ∨ (β∧δ)

Като разместим двата средни члена на дизюнкцията, накрая получаваме:

(α∧γ) ∨ (α∧δ) ∨ (β∧γ) ∨ (β∧δ)

С това доказахме логическата валидност на следната схема еквивалентност, която е разширена форма на дистрибутивния закон:

(α∨β) ∧ (γ∨δ) ⟺ (α∧γ) ∨ (α∧δ) ∨ (β∧γ) ∨ (β∧δ)

(Схемата е аналогична на дистрибутивния закон в аритметиката, ако си представим дизюнкцията като събиране, а конюнкцията като умножение – всеки член от първите скоби се комбинира с всеки от вторите.)

Напълно аналогично се показва, че в разширен вид другата форма на дистрибутивния закон също е валидна:

(α∧β) ∨ (γ∧δ) ⟺ (α∨γ) ∧ (α∨δ) ∧ (β∨γ) ∧ (β∨δ)

(Ако отново си представим дизюнкцията като събиране, а конюнкцията като умножение, тази форма на дистрибутивния закона не е валидна в аритметиката.)

Ще дадем пример за прилагането на разширените форми на закона на Де Морган и дистрибутивния закон, като опростим и сведем до нормална дизюнктивна форма следния израз:

¬[¬(p∧q∧r)→(r∧p)] ∧ (p→s)

Първо разлагаме двете импликации:

¬(p∧q∧r) ∧ ¬(r∧p) ∧ (¬p∨s)

След това прилагаме два пъти закона на Де Морган (един път в разширения му вариант):

(¬p∨¬q∨¬r) ∧ (¬r∨¬p) ∧ (¬p∨s)

Тук можем да съкратим първия член на конюнкцията („¬p∨¬q∨¬r“) по ii b), тъй като вторият й член („¬r∨¬p“) е част от първия – на „α“ в ii b) отговаря „¬r∨¬p“, а на „β“ – „¬q“:

(¬r∨¬p) ∧ (¬p∨s)

Прилагаме дистрибутивния закон в разширената му форма:

(¬r∧¬p) ∨ (¬r∧s) ∨ (¬p∧¬p) ∨ (¬p∧s)

Махаме едното повтарящo се „¬p“ в третия член на дизюнкцията:

(¬r∧¬p) ∨ (¬r∧s) ∨ ¬p ∨ (¬p∧s)

Сега можем да приложим ii a) върху последните два члена на дизюнкцията, в резултат на което последният член се съкращава:

(¬r∧¬p) ∨ (¬r∧s) ∨ ¬p

Отново прилагаме ii a) този път върху членовете „¬r∧¬p“ и „¬p“, съкращавайки първия от тях, с което формулата е максимално опростена:

(¬r∧s) ∨ ¬p

За да сведем един израз до нормална дизюнктивна форма, е достатъчно да използваме дистрибутивния закон само във вида му „α∧(β∨γ)“ ⟺ „(α∧β)∨(α∧β)“. С цел опростяване обаче понякога е целесъобразно да използваме и другата форма на закона („α∨(β∧γ)“ ⟺ „(α∨β)∧(α∨β)“). Ето един пример:

[q→(p→s)] ∧ [(p→s)∨q]
[¬q∨(p→s)] ∧ [(p→s)∨q]
(p→s) ∨ (¬q∧q)
p → s
¬p ∨ s

При прехода от втория в третия ред е използвана въпросната втора форма на дистрибутивния закон в обратната на обичайната посока („p→s“ играе ролята на „α“ в схемата). Това дава възможност след това да се съкрати противоречието „¬q∧q“ въз основа на iii a).

Можем да използваме логически преобразувания, за да доказваме или проверяваме дали два израза са логически еквивалентни. Те биха били такива, ако се свеждат до един и същ израз (евентуално в нормална дизюнктивна форма).

Освен това бихме могли да използваме логически преобразувания, за да доказваме или проверяваме дали някакъв израз е тавтология. Ако един от членовете на една дизюнкция е отрицание на друг неин член, т.е. ако част от дизюнкцията е „α∨¬α“, то тя е тавтология. За нормалната дизюнктивна форма това означава един от членовете ѝ да е буква за твърдение, а друг – нейното отрицание. Например ясно е, че „(p∧¬r)∨s∨¬s“ е тавтология, защото „s∨¬s“ винаги има стойност И, правейки по този начин цялата дизюнкция също винаги истинна (т.е. тавтология). Разбира се, ако искаме да разберем дали някакъв израз е тавтология чрез логически преобразувания и стигнем до израз, който очевидно има тавтологична форма, без да е в нормална дизюнктивна форма, не е нужно да продължаваме по-нататък с трансформациите. Например такъв би бил случаят, ако изразът, до който сме стигнали, има формата „α→α“, „α↔α“ или е дизюнкция, която съдържа „α∨¬α“ – тогава е очевидно, че той е тавтология.

Практиката показва, че в повечето случаи преобразуването на един израз в нормална дизюнктивна форма е най-лесно, ако преобразуванията се правят така да се каже отвън навътре, т.е. когато първо преобразуваме израза като цяло, после неговите главни части, после частите на тези части и т.н., а не обратно или без ред.

Нормална конюнктивна форма

За разлика от нормалната дизюнктивна форма, която е дизюнкция от конюнкции на букви за твърдения или техни отрицания, нормалната конюнктивна форма е конюнкция от дизюнкции на букви за твърдения или техни отрицания. Ето примери на формули в нормална конюнктивна форма:

(q∨r) ∧ (¬p∨¬q∨r) ∧ (s∨¬r)
r ∧ (q∨s) ∧ ¬p
p ∨ q ∨ r ∨ ¬w
¬r ∧ p

Когато са по-прости изрази, нормалната дизюнктивна и нормалната конюнктивна форми могат да съвпадат. Така е при последните две формули, които са едновременно в нормална конюнктивна и в нормална дизюнктивна форма. Предпоследната формула може да се разглежда както като нормална конюнктивна форма, която има един единствен член (цялата дизюнкция), така и като нормална дизюнктивна форма с четири члена – всеки буква за твърдение или отрицание на буква за твърдение. Последната формула може да се разглежда както като нормална конюнктивна форма, която има два члена (буквите за твърдения с или без отрицание), така и като нормална дизюнктивна форма, която има един единствен член (цялата конюнкция).

Всяка формула на пропозиционалната логика може да бъде сведена до нормална конюнктивна форма. Схемите еквивалентности, с които става това, са същите като при свеждането до нормална дизюнктивна форма, с тази разлика, че като правило се използва следната форма на дистрибутивния закон, която преобразува дизюнкциите в конюнкции:

α ∨ (β∧γ) ⟺ (α∨β) ∧ (α∨γ)

и нейният разширен вариант:

(α∧β) ∨ (γ∧δ) ⟺ (α∨γ) ∧ (α∨δ) ∧ (β∨γ) ∧ (β∨δ)

Освен това, когато изразът има формата на еквивалентност, е по-удобно последната да бъде разложена със схемата

α ↔ β ⟺ (α→β) ∧ (β→α)

а не със схемата

α ↔ β ⟺ (α∧β) ∨ (¬α∧¬β)

тъй като след последващото разлагане на двете импликации се получава израз от вида „(¬α∨β)∧(¬β∨α)“, който е конюнкция от дизюнкции, а не дизюнкция от конюнкции, както е при втората схема еквивалентност.

Като пример нека сведем до нормална конюнктивна форма израза

¬(p∨r) ↔ [q→(r∧¬s)]

Първо разлагаме материалната еквивалентност по посочения по-горе начин – заменяме я с конюнкция от импликации, след което се освобождаваме и от тях:

{¬(p∨r)→[q→(r∧¬s)]} ∧ {[q→(r∧¬s)]→¬(p∨r)}
{¬¬(p∨r) ∨ [q→(r∧¬s)]} ∧ {¬[q→(r∧¬s)] ∨ ¬(p∨r)}

Махаме двойното отрицание, разлагаме двете импликации и прилагаме закона на Де Морган върху израза „¬(p∨r)“:

[p ∨ r ∨ ¬q ∨ (r∧¬s)] ∧ {[q∧¬(r∧¬s)] ∨ (¬p∧¬r)}

Съкращаваме въз основа на ii a) „r∧¬s“ в първия член на главната конюнкция и прилагаме Де Морган и двойно отрицание във втория:

(p ∨ r ∨ ¬q) ∧ {[q∧(¬r∨s)] ∨ (¬p∧¬r)}

Прилагаме дистрибутивния закон във втория член на главната конюнкция, като разпределяме „¬p∧¬r“ в „q∧(¬r∨s)“:

(p ∨ r ∨ ¬q) ∧ [(¬p∧¬r) ∨ q] ∧ [(¬p∧¬r) ∨ ¬r ∨ s]

Въз основа на ii a) в последния член на главната конюнкция съкращаваме „¬p∧¬r“:

(p ∨ r ∨ ¬q) ∧ [(¬p∧¬r) ∨ q] ∧ (¬r ∨ s)

Прилагаме дистрибутивния закон върху втория член на главната конюнкция, като разпределяме „q“ в „¬p∧¬r“:

(p ∨ r ∨ ¬q) ∧ (q ∨ ¬p) ∧ (q ∨ ¬r) ∧ (¬r ∨ s)

Изразът вече е в нормална конюнктивна форма. За да видим дали не може още да се опрости, подреждаме членовете на дизюнкциите по азбучен ред:

(p ∨ ¬q ∨ r) ∧ (¬p ∨ q) ∧ (q ∨ ¬r) ∧ (¬r ∨ s)

Никой от членовете на конюнкцията не съдържа в себе си друг от членовете, поради което не могат да бъдат направени допълнителни съкращения с ii b), така че това е нормалната конюнктивна форма, до която стигаме.

Също като свеждането до нормална дизюнктивна форма, свеждането до нормалната конюнктивна форма може да се използва, за да се провери дали два израза са логически еквивалентни. Освен това, свеждането до нормалната конюнктивна форма може да се използва, за да се покаже, че дадена формула е противоречие. Това ще е факт, ако получената конюнкция съдържа буква за твърдение и нейното отрицание. Противоречие е например формулата „(p∨¬r)∧s∧¬s“ поради участието на „s∧¬s“ в нея. Разбира се, ако в процеса на преобразуване стигнем до израз с формата на очевидно противоречие, преди да сме стигнали до нормална конюнктивна форма, не е нужно да продължаваме нататък. Например не е нужно да свеждаме формулата

p ∧ ¬q ∧ ¬[q∨(¬r∧p)] ∧ [q∨(¬r∧p)]

до нормална конюнктивна форма, за да се убедим, че е противоречие, тъй като участващата в главната конюнкция подформула „¬[q∨(¬r∧p)] ∧ [q∨(¬r∧p)]“ има формата „¬α∧α“, което прави цялата конюнкция винаги неистинна.

Задачи

(Изтеглете задачите като pdf.)
(1) Определете дали изразът е в нормална дизюнктивна форма, в нормална конюнктивна форма, в двете едновременно или в нито една от двете.
1) s ∨ ¬q ∨ s ∨ ¬r
2) (¬p∧r) ∨ (q∧¬q) ∨ s
3) (r∨¬q) ∧ ¬p ∧ (q∨¬(r∨q)∨¬s)
4) ¬q ∨ ¬(p∧q) ∨ (¬r∧q)
5) ¬r ∧ q ∧ ¬s ∧ r
6) ¬q ∨ (¬r∧s∧p) ∨ ¬r
7) q ∧ (r∨¬s∨¬p) ∧ ¬r
8) ¬(r∧q) ∨ (¬p∧q) ∨ r
9) (p∧¬q∧r) ∨ p ∨ ¬q ∨ r
10) (p∧q) ∨ (p∧¬q) ∨ ¬(p∧q) ∨ (¬p∧¬q)
(2) Преобразувайте следните формули в нормална дизюнктивна форма и ги опростете доколкото е възможно:
1) (p∧¬p∧q) ∨ [q∧(q∨r)] ∨ q
2) ¬q → {¬p ∧ [q∨(¬p∧¬q)]}
3) ¬[¬(q→r)∨(r∧q)] ∨ ¬(p→q)
4) ¬q → {(r→q) → ¬[¬r∧(¬q∨¬p)]}
5) (p↔q) ∧ (q↔r)
6) (¬p→q) ∧ (¬p→¬q)
7) ¬{[p∧(p→q)]→(q∧¬r)} → q
8) [(p∧¬q)∨¬p] → ¬[(r∨q)→¬q]
9) s ↔ (q∧r)
10) (p∧q) ↔ (q→r)
11) [(r→¬s)→r] ∧ {(r∧s)∨[¬r→¬(p→q)]}
12) (p∧¬r∧p) ∨ {[(q→q)→(p→q)] → q}
13) (p↔q) → (r↔q)
14) [p∧¬(s→q)] ∨ [(p∨q)∧(s∨p)] ∨ (s∧¬q)
15) [(p→q)→p] ↔ ¬p
16) [(p→q)→q] ∧ ¬(p→¬q)
17) {¬[r∨¬(s→p)] ∧ (s→¬p)} → (r∧s)
18) p → [q↔(r∧s)]
19) ¬(¬r→¬{q∨¬[p∨¬(q∨r)]})
20) p ↔ (r↔q)
(3) Проверете чрез логически преобразувания дали следните двойки формули са логически еквивалентни.
1) ¬(¬p→q)
¬(¬q→p)
2) (p→q) → ¬p
¬p ∧ ¬q
3) (p→q) ∨ (r→q)
r → (p→q)
4) p → (¬q∧r)
(p→¬q) ∧ (p→r)
5) (p∨q) ∧ ¬(p∧q)
p ↔ ¬q
6) p → [(p∧¬q)→r]
r ∨ q ∨ ¬p
7) (p∧¬q) → r
¬r → (¬p∨q)
8) (p∧q) → (r∧s)
[(p∨q)→s] ∧ [¬r→(¬q∧¬p)]
9) ¬p ∧ ¬q ∧ ¬r ∧ ¬s
¬(¬p→s) ∧ ¬(¬q→r)
(4) Определете с логически преобразувания кои от следните твърдения са логически еквивалентни помежду си и кои не:
1) Иван ще се пропие, ако Мария го изостави или го уволнят.
2) Иван ще се пропие, ако Мария го изостави, или ще се пропие, ако го уволнят.
3) Иван ще се пропие, ако Мария го изостави и го уволнят.
4) Иван ще се пропие, ако Мария го изостави, но ще се пропие и ако го уволнят.
5) Ако Мария изостави Иван, то ако го уволнят, Иван ще се пропие.
(5) Докажете с логически преобразувания, че следните формули са тавтологии.1
1) ¬(p∨q) → ¬p
2) (p→q) → [(r∨p)→(r∨q)]
3) [p∨(q∧¬r)] → [(p∨q)∧(r→p)]
4) [(p→q)∧(r→s)] → [(p∨r)→(q∨s)]
5) ¬p → ¬(p∧q)
6) ¬p → [(p→q)∨q]
7) [p∧(q∨r)] → [(p∧q)∨(p∧r)]
8) [(p→q)∨r] → ¬[(p∧¬q)∧¬r]
1. Формулите са същите като тези в задача (1) от „1.4 Доказателство чрез допускане на противното“. Може да сравните двата метода. ↩