Введение в логику. Знакомство с формальной логикой и таблицами истинности, страница 7

4     Законы де Моргана                             1 (a v 6) = 1 a л 1 A;        ](«AA) = lavlA

5     Закон двойного отрицания                            1 ] я = a
(инволюции)

8     Законы идемпотентности                 a v a = a;     a /\ a = а

9     Законы поглощения                          a v (а л Z») = а;      а л (a v £) = а                             ;

Пример 1

Доказать, что о v ] а = 1.

Доказательство проведем, применив к заданному выражению закон де Моргана и операцию с переменной и ее инверсией:

я v 1 в = {4} = 1 (1 я л я) = {6} = 1 0 = 1.

20

Пример 2

Доказать, что 1 (a v b) л (а л 1 Ь) = 0.

Доказательство проведем, применив к заданному выражению законы алгебры логики в следующей последовательности — закон де Моргана, сочетательный закон, операцию с переменной и ее инверсией, а затем дважды — свойство операции конъюнкции:

] (a v Ь) л (а л 1 Ь) = {4} = 1 а л 1 b л (а л 1 Ь) = {2} = 1 а л а л 1 b л 1 b = {6} = = 0 л 1 b л 1 b = {7} = 0 л 1 b = {7} = 0.

Пример 3

Упростить логическую функцию:

F(a, b, с) — ] b л 1 с л (a v 1 д).

Для этого последовательно применим операцию с переменной и ее инверсией и свойство операции конъюнкции:

F(a, b, с) = 1 b л 1 с л ( a v 1 а) = {6} = 1 b л 1 с л 1 = {7} = 1 b л 1 с.

Пример 4

Упростить логическую функцию:

F(a, b, с) = а л b л! cv av b.

Заполним таблицу истинности (табл. 5.2) и выпишем значения функции на соответ­ствующих наборах логических переменных.

F(a, b, с) = алЬл~\счачЬ = {9} = ачЬ.

Таблица 5.2

а            Ь            с       F=аv b

⁰⁰⁰_____°                                         /"(0,0,0) = 0 + 0 = О

001              0                                   /40,0,1) = 0 + 0 = 0

——————\————-—————j——              /-(0,1,0) = 0+1 = 1

————————— ———————————             /"(0,1,1) = 0 + 1 = 1

⁰¹¹¹   /"(1,0,0) = 1 + 0 = 1

¹            0            0_____!                                              /-(1,0,1) = 1 + 0 = 1

1011   /(1,1,0) = 1 + 1 = 1

—i——J   —5———J—     /"(1,1,1) = 1 + 1 = 1 1111

Законы логики также применяются для построения логических функций по табли дам истинности. При этом нужно руководствоваться следующим правилом:

Для каждой строки таблицы истинности с единичным значением построить минтерм (конъюнкцию переменных), при этом переменная должна встретиться только один раз (без отрицания или с отрицанием). Объединить все минтермы операцией дизъ­юнкции.

Если в таблице истинности переменные имеют нулевые значения в строке, то в мин-терм они входят с отрицанием, а переменные, имеющие значение единица, входят в минтерм без отрицания.

Пример 5

По заданной таблице истинности (табл. 5.3) построить логическую функцию.

Таблица 5.3

Выберем строки, в которых F= \. Построим для них минтермы: Q    строка 1:1ял1бл~|с; Q    строка 2: 1 а л 1 Ъ л с.

Объединим минтермы:

F(a, b, с) = 1ал1^л]су1ал1^лс.

Упростим логическую функцию:

F(a, b, с) = ~\ а л~\b a~\cv~\a л~\b лс= {3} = ~\a /\~\ b л(\cv с) = {7, 6}  =

= 1 а л 1 b = {4} = 1 (a v b).

Итак, мы получили логическую функцию:

F(a, b, с) = ] (a v b).

22

Задание 1

Упростите логические функции: I 1. F(c) = 11 с v 0.

Г                    =

2. F(F) = ~\(\FvF).

Задание 2

Упростите логическую функцию
«                                                         F(a, b, с) = 1 a v с v ] (а л Ь),

применив последовательно законы {4, 1, 8, 4}. Заполните таблицу истинности (табл. 5.4). Выпишите значения функции на соответствующих наборах логических переменных.

\

..______                                ___                                                                                  -..}

Таблица 5.4

а        Ь        с

-—-—--————————     то,о) = —————

——————————————————————————————                             /-(0,0,1) = _________

I              °         °         *______________________                                                                                    /"(0,1,0)=__________