Равносильные формулы логики высказываний

2062
0
08 июля 2009
(37.2.) Рассмотрим понятия дизъюнкции конъюнкций из аргументов и их отрицаний, разберем специфику формул, представляющих одну и ту же булеву функцию.
Предположим, что булева функция определена таблицей истинности. В этом случае можно составить соответствующую ей формулу. Например, обозначим таблицу

 

(37.1)

 

37.2_html_4acb0bb4.gif

37.2_html_m593bc453.gif

37.2_html_29fa9cb0.gif

37.2_html_228cc5cb.gif

37.2_html_228cc5cb.gif

37.2_html_228cc5cb.gif

37.2_html_228cc5cb.gif

37.2_html_m769c0de4.gif

37.2_html_m769c0de4.gif

37.2_html_m769c0de4.gif

37.2_html_228cc5cb.gif

37.2_html_m769c0de4.gif

37.2_html_m769c0de4.gif

37.2_html_m769c0de4.gif

37.2_html_228cc5cb.gif

 

Для того, чтобы построить37.2_html_29fa9cb0.gifнам понадобятся строки с37.2_html_m165d96af.gif- строки 1, 4.

Формула37.2_html_29fa9cb0.gifпостроена как дизъюнкция конъюнкций.

О: Дизъюнкция конъюнкций из аргументов и их отрицаний именуется нормальной дизъюнктивной формой.

Т: Всякую булеву функцию37.2_html_m7f54c688.gifпеременных можно обозначить в виде нормальной дизъюнктивной формы.

Помимо дизъюнктивной формы, таблице (37.1) в силу определения эквивалентности соответствует37.2_html_3a2af628.gifЭто говорит о том, что одну и ту же булеву функцию можно задать разными формулами.

О: Формулы, которые представляют одну и ту же булеву функцию, носят название эквивалентных или равносильных.

В ОК 37.2. обозначены простейшие равносильности, которые применяют для составления более простых формул.

Для того, чтобы осуществить преобразование формул, наряду с равносильной 1 — 12 нужны следующие две теоремы.

Т.1 (об использовании формулы вместо переменной):

Предположим, что37.2_html_6f0d387c.gif- некоторая формула. В этом случае, при использовании вместо37.2_html_31c4c10b.gifформулы37.2_html_6416a54.gifравносильность37.2_html_5b1d9db2.gifсохраняется.

Т.2 (о замене подформул): Допустим, что37.2_html_2e880892.gifявляется формулой, которая включает37.2_html_432ea6e.gif- результат замены в ней37.2_html_m606089c0.gifна37.2_html_6d37a1c9.gif.

Теоремы представляют собой следствие сохранения таблиц истинности интересующих нас формул.

Пример 1: Представить доказательство того, что37.2_html_m5b05fc5.gif

В соответствии с теоремой 1 и на основании равносильностей 5 обозначим37.2_html_14bac35f.gifВ силу теоремы 2 и равносильности 1 теперь37.2_html_m36b74b00.gif

Пример 2: Записать формулу, используя таблицу истинности:

 

37.2_html_m5f00691d.gif

37.2_html_m31e53475.gif

37.2_html_m26f73c9c.gif

37.2_html_6bcc6ebb.gif

37.2_html_45008100.gif

37.2_html_m769c0de4.gif

37.2_html_m769c0de4.gif

37.2_html_m11104929.gif

37.2_html_228cc5cb.gif

37.2_html_m769c0de4.gif

37.2_html_m769c0de4.gif

37.2_html_m769c0de4.gif

37.2_html_m769c0de4.gif

37.2_html_228cc5cb.gif

37.2_html_m769c0de4.gif

37.2_html_228cc5cb.gif

37.2_html_m769c0de4.gif

37.2_html_m769c0de4.gif

37.2_html_228cc5cb.gif

37.2_html_228cc5cb.gif

37.2_html_228cc5cb.gif

37.2_html_228cc5cb.gif

37.2_html_m769c0de4.gif

37.2_html_m769c0de4.gif

37.2_html_228cc5cb.gif

37.2_html_m769c0de4.gif

37.2_html_228cc5cb.gif

37.2_html_m769c0de4.gif

37.2_html_m769c0de4.gif

37.2_html_228cc5cb.gif

37.2_html_228cc5cb.gif

37.2_html_228cc5cb.gif

37.2_html_228cc5cb.gif

37.2_html_228cc5cb.gif

37.2_html_228cc5cb.gif

37.2_html_228cc5cb.gif

 

Отметим представление соответствующей таблице булевой функции в виде нормальной дизъюнктивной формы, применяя строки c37.2_html_11cfb08e.gif:

 

37.2_html_640a0fe2.gif

 

Данная формула может быть упрощена с помощью равносильностей 2-4, 7, 9:

 

37.2_html_1b53fa2_show.gif

37.2_html_4a98dc52.gif

 

Подобные задачи следует решать при синтезе контактных схем. Они формулируются также в теории распознавания образов, где устанавливается, в соответствии с определенной совокупностью высказываний, взаимосвязь между причинами и следствиями. Использование данной теории актуально для геологии, химии, медицины, социологии.



(38.4.) Сформулируем понятие конечного автомата, обозначим входной алфавит, выходной алфавит, алфавит состояний, функцию переходов, функцию выходов, на рисунке изобразим граф переходов.
2528 0
(38.3.) Большинство графов, которые используются в приложениях (например, графы сортировок, классификаций) предполагают наличие диаграмм, именуемых деревьями. Связный неориентированный граф без циклов, в частности, предполагающий отсутствие петель и кратных ребер, именуют деревом. Несвязный неориентированный граф без цикла — лес, его связные компоненты являются деревьями.
7352 0
(38.2.) В рамках обозначенной темы рассмотрим случай определения связного неориентированного мультиграфа в качестве эйлерова и гамильтонова графа.
9216 0

    Вы должны авторизоваться, чтобы оставлять комментарии.

    Радиомастер
    © 2005–2017 radiomaster.ru
    admin@radiomaster.ru
    При использовании материалов данного сайта прямая и явная ссылка на сайт radiomaster.ru обязательна. 0.2533 s