Page 60 - 4570

59

одночлен у побудованій ДНФ надасть значення T лише в своєму рядку. Отже,
побудована таким чином ДНФ є рівносильною до функції поданою таблицею
істинності. Для побудови КНФ дії аналогічні.
Приклад 2.17. Утворити ДНФ та КНФ для функції логіки висловлювань,
що подана таблицею істинності.

А 1 А 2 f

F F T
F T T

T F T
T T F

Розв’язання. Для рядків таблиці із значенням T для f записуємо
елементарні кон’юнкції А 1  А 2, А 1  А 2, А 1   А 2, які зв’язуємо між
собою диз’юнкцією. Одержимо ДНФ:
f = (А 1  А 2)  (А 1  А 2)  (А 1  А 2).
КНФ для даної функції – f = А 1  А 2.

4. Дедуктивні висновки у логіці висловлювань

У логіці висловлювань правила висновку використовують, щоб виводити
одні істинні речення з інших істинних речень. У коректному дедуктивному
виведенні висновок з необхідністю випливає з посилок.
Означення 2.19. Логічним наслідком висловлювання A є висловлювання
B , якщо формула A  B є тотожно істинною. Це визначення може бути
,
узагальнене для випадку A A ,..., A висловлювань, якщо A  A  ...  A  B –
1 2 n 1 2 n
тотожно істинна формула.
Приклад 2.18. Показати, що висловлювання (A B )  C є логічним
наслідком висловлювання A C .
Розв’язання. Доведемо, що формула A  C  (A B )   )C є
(
загальнозначущою. Для її доведення використаємо тотожності логіки
висловлювань та еквівалентні перетворення:
(A  C)  ((A  B)  C) = (A  C)  (A  B)  C =
= A  C  (A  B)  C = A  C  C  (A  B) =
= A  (A  B)  T = T.
Отже, формула A  C  (A B )   )C є загальнозначущою, а A C
(
– логічний наслідок.
Означення 2.20. Дедуктивним висловлюванням називають висновок
формули B з формули A , що ґрунтується на тому, що B є логічним наслідком
A .
Приклад 2.19. Довести правильність міркування за дедукцією –
«Постанова Кабінету Міністрів ухвалюється, якщо за неї голосує більшість