yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->3.4 Построение заданных составных высказываний

Дискретная математика

3.4 Построение заданных составных высказываний

 

В ряде практических случаев возникает необходимость построения составных высказываний с заданной таблицей  истинности.  Один  из методов построения дает следующая теорема.

Теорема.  Всякая логическая функция, кроме const "0" может быть представлена в виде дизъюнкции  основных  конъюнкций. Такое- представление  называется  "совершенной  дизъюнктивной  нормальной формой" представляемой функции (СДHФ ).  Const "0" можно представить как p /\ ~p.

 

Таблица основных конъюнкций  для трех аргументов

 

----T---T---T---------------T------------¬

¦ p ¦ q ¦ r ¦ осн-ые кон-ции¦ строка ист.¦

+---+---+---+---------------+------------+

¦ 1 ¦ 1 ¦ 1 ¦ p /\ q /\ r   ¦     1      ¦

¦ 1 ¦ 1 ¦ 0 ¦ p /\ q /\~r   ¦     2      ¦

¦ 1 ¦ 0 ¦ 1 ¦ p /\~q /\ r   ¦     3      ¦

¦ 1 ¦ 0 ¦ 0 ¦ p /\~q /\~r   ¦     4      ¦

¦ 0 ¦ 1 ¦ 1 ¦~p /\ q /\ r   ¦     5      ¦

¦ 0 ¦ 1 ¦ 0 ¦~p /\ q /\~r   ¦     6      ¦

¦ 0 ¦ 0 ¦ 1 ¦~p /\~q /\ r   ¦     7      ¦

¦ 0 ¦ 0 ¦ 0 ¦~p /\~q /\~r   ¦     8      ¦

L---+---+---+---------------+-------------

 

Для того, чтобы получить функцию с заданной таблицей истинности, достаточно выбрать в таблице основные конъюнкции из строк,  в которых значения функции равны 1 и связать их знаками дизъюнкции.

 

Пример.  Построить составное высказывание, которое  истинно  в строках 2 и 6 (т.е. с таблицей истинности 01000100).

А = (p /\ q /\~r)\/(~p /\ q /\~r) - выбираем из  таблицы  основные конъюнкции из строк 2 и  6  и  связываем  их  дизъюнкцией.

Полученное высказывание можно упростить, используя теоретико-множественное преобразование высказывания (будет рассмотрено ниже).

 

 

16