Логические формулы

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

... Смотреть решение »

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

Две формулы $F_1 и F_2$ называются равносильными, если они имеют одинаковое значение “и” или “л” при одинаковых наборах пропозициональных переменных, включаемых в $F_1  и  F_2,  т.е . F_1 = F_2$ . Если две формулы равносильны, то они эквивалентны, т.е. $(F_i\leftrightarrow F_i)$. Если формула $F$ имеет вхождением подформулу $F_i$, для которой существует эквивалентная подформула $F_j, т.е. F_i \leftrightarrow F_j$, то возможна подстановка всюду в формулу $F$ вместо формулы $F_i$ подформулу $F_j$ без нарушения истинности формулы $F$.

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

Пример 1: Дано $F=(F_1\rightarrow F_2) \rightarrow ((F_2\rightarrow F_3) \rightarrow (F_1∨F_2 \rightarrow F_3))$.

Выполнить преобразования для упрощения алгебраического выражения.

Решение.

1) Удалить всюду логическую связку  $“\rightarrow ”$ (см. эквивалентные формулы ):

$F = \left \rceil \right. (\left \rceil \right. \!\! F_ 1\vee F_ 2)\vee (\left \rceil \right. \! ... Смотреть решение »

Метод квайна (Куайна)

• Определение. Элементарная конъюнкция К называется импликантом функции f, если для всякого набора а = (а1, а2, …, an) из 0 и 1 условие К(а)=1 влечет f(a)=1.
• Определение. Импликант К функции f называется простым, если выражение, получающееся из него выбрасыванием любых множителей, уже не импликант функции f.
• Всякий импликант функции f есть часть функции f.
• Теорема. Всякая функция реализуется дизъюнкцией всех своих простых импликант.
• Определение.Сокращенная ДНФ функции f есть дизъюнкция всех простых импликант функции f.
• Утверждение. Всякая функция f реализуется своей  сокращенной ДНФ.
• Для всякой функции, не равной тождественно нулю, существует единственная сокращенная ДНФ.
• Теорема (Куайна). Если в СДНФ функции f провести все операции неполного склеивания, а затем все операции поглощения и удаления дублирующих членов, то в результате получится сокращенная ДНФ функции f.

Алгоритм Куайна построения сокращенной ДНФ
1.    Получить СДНФ функции.
2.    Провести все операции неполного склеивания.
3.    Провести все операции поглощения.

Пример. Минимизировать функцию f=1111010010101111.
Решение.
1.   ... Смотреть решение »