Таблица на истинността

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

Когато имаме 2 променливи: A и B са възможни 2⁴ = 16 функции от две променливи, които се различачават една от друга по своя резултат. Аналогично, възможни са 2² = 4 функции от една променлива и 2¹ = 2 функции от нула променливи

Прилагам една обобщена таблица на повечето логически функции:

Таблица на истинността	Име	Знаци	Чете се:	Пояснение	Свойства
A ¬A 0 1 1 0	отрицание, инверсия, логическо не		не	Дава резултат противо-положен на изходния	¬(¬A)=A ¬0=1 ¬1=0
A B A B 0 0 0 0 1 0 1 0 0 1 1 1	конюнкция, логическо и, логическо умножение		и	Дава резултат истина само когато всички операнди са истина	(AB)C=A(BC)=ABC AB=BA A0=0; A1=А AA=A A(¬A)=0
A B A B 0 0 0 0 1 1 1 0 1 1 1 1	дизюнкция, логическо или, включващо или		и/или, vel (лат.)	Дава резултат лъжа само когато всички операнди са лъжа	(AB)C=A(BC)=ABC AB=BA A0=А; A1=1 AA=A A(¬A)=1
A B A B 0 0 0 0 1 1 1 0 1 1 1 0	изключващо или, събиране по модул 2, равнозначност		или, aut (лат.)	Дава “истина” само когато операндите имат различна истинност.	(AB)C=A(BC)=ABC AB=BA A0=A; A1=¬А AA=0; A(¬A)=1 AB=(¬A).B+A.(¬B)>=(AB)((¬A)(¬B))
A B A | B 0 0 1 0 1 1 1 0 1 1 1 0	щрих на Шефер, логическо и-не	A | B A NAND B	не … и не	Лъжа само когато и двата операнда са истина	(A|B)|C≠A|(B|C) A|B=B|A A|0=1; A|1=¬A A|A=¬A; A|(¬A)=1 A|B=(¬A).(¬B)=¬(AB)
A B A ↓ B 0 0 1 0 1 0 1 0 0 1 1 0	стрелка на Пирс, логическо или-не	A↓ B A NOR B	не … или не	Истина само когато и двата операнда са лъжа	(A↓B)↓C≠A↓(B↓C) A↓B=B↓A A↓0=¬A; A↓1=0 A↓A=¬A; A↓(¬A)=0 A↓B=(¬A).(¬B)=¬(AB)
A B A↔ B 0 0 1 0 1 0 1 0 0 1 1 1	равносилност, еквивалентност, равноистинност		равноистинно, равносилно, еквивалентно	Дава “истина” само когато операндите имат една и съща истинност.	A↔B=¬(AB)= A.B+(¬A).(¬B)=(A(¬B))((¬A)B)
A B A→B 0 0 1 0 1 1 1 0 0 1 1 1	импликация материална импликация заключение следствие		имплицира, ако … то, следователно	Дава “лъжа” само когато първия операнд е истина, а втория – лъжа	A→B=(¬A)→(¬B) A→B=(¬A)B (A→B)(B→A)=A↔B
A B A←B 0 0 1 0 1 0 1 0 1 1 1 1	достатъчност		достатъчно	Дава “лъжа” само когато първия операнд е лъжа, а втория – истина

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

• Функцията на Пирс е отрицание на дизюнкцията.
• Функцията на Шефер е отрицание на конюнкцията.
• Функцията равносилност е отрицание на изключващото или.

Ако A и B са двоични числа, то таблицата за тяхното събиране ще има същия вид, както таблицата на истинността на изключващото или (1+1=0 с пренос на 1 в старшия разред).Затова изключващото или се нарича още сума по модул 2.

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

Класификация на
формулите. Тавтология. Равноистинност.

В зависимост от вида на таблицата на истинността булевите формули се класифицират освен по броя на променливите ( от 0 до n ) и по това какво е написано в последната колона. Ако там има само TRUE (1), то тогава тази формула се нарича “тавтология” (общозначима или тъждествено истинна). В противен случай, тя ще бъде “необщозначима” формула. Ако там има само FALSE (0), такава формула се нарича “неизпълнима“, в противен случай би била “изпълнима” формула. “Неутралните” формули съдържат както TRUE, така и FALSE.

Или да обобщим в таблицата:

Име на функцията	Определение (съдържание на дясната колона)	Пример
тавтология (общозначима)	съдържа само TRUE	TRUE FALSE
изпълнима	съдържа поне едно TRUE	¬А
неизпълнима	съдържа само FALSE	A&¬А
необщозначима	съдържа поне едно FALSE	ABC
неутрална	съдържа поне едно TRUE и поне едно FALSE	(A→B)→C

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

Правило на равноистинността: Ако A (…)↔B (…) е тавтология, то тогава формулите A (…) и B (…) равноистинни, и обратното.

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

Принцип на дуалността

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

Съкращаване на подобните членове

В булевата алгебра има метод, който по същността си е подобен на съкращаването на подобните членове в обикновената алгебра. Ролята на събирането играе дизюнкцията, ролята на умножението – конюнкцията. Съответно формулите свързани със знака “” се наричачат “събираеми”, а тези със символа “&” – “множители”. Вместо числени коефициенти пред променливите ще липсва или ще има отрицание. Например:

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

1. отрицание
2. конюнкция
3. дизюнкция.

Такива формули са наричат дизюнктивни форми.

Закон за слепването

X Y X ( ¬Y) = X

(X Y) (X ( ¬Y)) = X

Премахване на излишните отрицания (Закон за двойното отрицание)

По един прост принцип могат да се съкратят многократните отрицания: ¬ ¬ X = X. Така, от нечетен брой отрицания остава едно, а при четен – нито едно

Закони за поглъщането при множителите

	Формула	Обяснение	Пример
1	X&TRUE = X	Ако сред множителите има TRUE, то той може да да бъдат отстранени напълно	x y&TRUE = x y
2	X&FALSE = FALSE	Ако сред множителите има FALSE, то цялото събираемо се превръща в FALSE	x t&y&FALSE = x FALSE
3	X&X = X	Ако има два (или повече) еднакви множители в едно събираемо, то може просто да се задраскат всички, освен едно	x ¬t&¬t&y&¬t = x ¬t&y
4	X&¬X = FALSE	Ако сред множителите има два (или повече) множители, където една и съща променлива е със знак “¬” и без него, то цялото събираемо се превръща в FALSE	x t&y&¬t = x FALSE

Закони за поглъщането при събираемите

	Формула	Обяснение	Пример
1	X TRUE = TRUE	Ако сред събираемите има TRUE, то цялата формула се превръща в TRUE	x&z&t TRUE = TRUE
2	X FALSE = X	Ако сред събираемите има FALSE, то цялото събираемо може да се премахне, ако не е последно – тогава остава само FALSE	x FALSE y = x y.
3	X X = X	Ако има две (или повече) еднакви събираеми, то може просто да се задраскат всички, освен едно	x x y = x y
4	X ¬X = TRUE	Ако сред събираемите има две еднакви събираеми, но едното със знак “¬” , а другото без, то цялото събираемо се превръща в TRUE	z ¬z y = TRUE

Закони на де Морган

За истински основател на логическия анализ на отношенията се смята английския логик и математик Август де Морган (1806-1871). Неговата "Формалната логика или изчисление нанеобходимите и вероятностни умоключения" е публикувана през същата година с "Математически анализ на логиката" от Джордж Бул. В този си труд де Морган първи описва тези закони, наречени по-късно на негово име:

¬(X Y) =( ¬X) ( ¬Y)

¬(X Y) =( ¬X) (¬Y)

Допълнителни закони на де Морган:

X ↔ Y = (X →Y) (Y →X)

X →Y= ¬X Y

Съвършена дизюнктивна нормална форма

Оказва се, че всяка булева функция с произволен брой променливи може да се представи като комбинация от функции с 1 и 2 променливи. Това позволява да се съставят сложни микросхеми само от няколкои типови елементи.

Всяка функция може да се представи в дизюнктивна форма.

Има прост метод за построяване на такава формула по таблицата на истинността, а резултатът се нарича съвършена дизюнктивна нормална форма (СДНФ).

Как става това ще стане ясно в хода на доказателството, че всяка логическа функция от N променливи може да се представи чрез операциите &, , ¬.

Нека е дадена произволна булева функция f(x₁, x₂, x₃,…,x_N) като таблица на истинността:

Да вземем функция от 1 променлива:

Ако A_i,j = TRUE, то S_i,j(x_i) = x_i

Ако A_i,j = FALSE, то S_i,j(x_i) = ¬x_i

Тогава функцията може да бъде представена в вида:

(S_1,1(x₁) & S_2,1(x₂) & S_3,1(x₃) & … & S_N,1(x_N) & F₁)

(S_1,2(x₁) & S_2,2(x₂) & S_3,2(x₃) & … & S_N,2(x_N) & F₂)

(S_1,3(x₁) & S_2,3(x₂) & S_3,3(x₃) & … & S_N,3(x_N) & F₃) (1)

…

(S_1,M(x₁) & S_2,M(x₂) & S_3,M(x₃) & … & S_N,M(x_N) & F_M)

На всеки ред във формулата (1), представена само от , ¬ и&, съответства ред от таблицата.

Остава да се докаже, че дясната част (1) действително е равна на дадената функция.
Да вземем произволен ред от таблицата:

Ще се убедим, че стойността на функцията F_j наистина е равна на стойността на дясната част (1) когато стойностите на променливите са равни на стойностите, показани в тари ред: x₁ = A_1,j, x₂ = A_2,j и т.н.,или, x_i = A_i,j заi = 1, 2, 3,…, N.

Помощни функции за този ред:

Ако A_i,j = TRUE, то S_i,j(x_i) = x_i = A_i,j = TRUE

Ако A_i,j = FALSE, то S_i,j(x_i) = ¬x_i = ¬A_i,j = ¬FALSE = TRUE

Тоест, за избранотоjи за всякоiе вярно:

S_i,j(x_i) = TRUE (2).

Вземаме в (1) j-ия ред, заместваме в него (2) и прилагаме законът за поглъщането: x & TRUE = x:

S_1,j(x₁) & S_2,j(x₂) & S_3,j(x₃) & … & S_N,j(x_N) & F_j = F_j & TRUE & TRUE & TRUE … & TRUE = F_j

Сега да вземем в (1) кой да е друг ред, освен j-тия. Нека той има номер k. Тъй като всички редове на таблицата съдържат различни набори A_i,j, то поне в една колона ще има разлика. Нека разликата е в n-тата колона:

A_n,j ≠ A_n,k

Оттук:

Ако A_n,j = TRUE, то A_n,k = FALSE, значи S_n,k(x_n) = x_n = A_n,k = FALSE

Ако A_n,j = FALSE, то A_n,k = TRUE, значи S_n,k(x_n) = ¬x_n = ¬A_n,k = ¬TRUE = FALSE

Тоест, за избраните n и k е вярно:

S_n,k(x_n) = FALSE (3)

Вземаме в (1) k-тия ред, вмъкваме в него (3) и прилагаме законите на поглъщането x & FALSE = FALSE и FALSE & x = FALSE:

S_1,k(x₁) & S_2,k(x₂) & … & S_n,k(x_n) & … & S_N,k(x_N) & F_k = S_1,k(x₁) & S_2,k(x₂) & … & FALSE & … & S_N,k(x_N) & F_k =FALSE

По този начин, стойността на всички редове на СДНФ, освен на j-тия е равна на FALSE за сметка на поне една разлика в набора променливи. И само на j-тия
ред е равна на F_j.

По законите на поглъщането: x FALSE = x и FALSE x = x и формула (1) се превръща в:

(FALSE)

(FALSE)

…

(FALSE)

(F_j)

(FALSE)

…

(FALSE) = F_j

Разгледахме произволен j-ти ред от таблицата и се убедихме, че за набора от променливи, намиращи се на този ред,стойността на функцията съвпада със стойността на формула (1). Същото разсъждение може да се повтори за всички останали редове, незявисимо колко са. По този начин, стойността на функцията съвпада със стойността на формула (1) за всички възможни набори променливи. Което трабваше да се докаже.

В формула (1) редовете, в които F_j = FALSE може да се премахнат (вижте по-горе в абзаца Закони за поглъщането при събираемите, правило 2).
А в редовете, в които F_j = TRUE може да се пропусне F_j (виж. правило 1, Закони за поглъщането при множителите).

Накрая, след всичките тези съкращения се получава съвършената дизюнктивна нормална форма (СДНФ).

Пример

Съвършена дизюнктивна нормална форма (СКНФ)

Конюнктивната форма е формула, подобна на дизюнктивната форма, само че в нея е променен реда на операциите. Отначало се изпълняват сериите себирания, а после – серията умножения. Например:

(ab¬c) & (a¬bc) & (a¬b¬c)

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

Да обобщим:

За получаване на СДНФ на основата на таблица на истинността е необходимо:

• Всеки от входните набори, за които булевата функция получава стойност 1 да се представи във вид на елементарно произведение (конюнкция), при което ако променливата е равна на 0, то тя влиза в конюнкцията с отрицание, а ако е 1 – без отрицание.
• Получените елементарни конюнкции се обединяват със знаци за дизюнкция

За получаване на СКНФ на основата на таблицата за вярност е необходимо:

• Всеки от входните набори, за които булевата функция получава стойност 0 да се представи във вид на елементарна дизюнкция, при което ако променливата е равна на 1, то тя влиза в конюнкцията с отрицание, а ако е 0 – без отрицание.
• Получените елементарни дизюнкции се обединяват със знаци за конюнкция

Следва трета част