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

Две формулы $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. \!\! ( \left \rceil \right. \!\! F_ 2\vee F_ 3)\vee (\left \rceil \right. \!\! (F_ 1\vee F_ 2) \vee F_ 3))$;

2) Опустить отрицание на элементарные формулы по закону де Моргана:

$F =F_ 1\left \rceil \right. \!\! F_ 2\vee F_ 2\left \rceil \right. \!\! F_ 3\vee \left \rceil \right. \!\! F_ 1\left \rceil \right. \!\! F_ 2\vee F_ 3$;

3) Выполнить преобразование по закону дистрибутивности:

$F =( F_ 1\vee \left \rceil \right. \!\! F_ 1) \left \rceil \right. F_ 2\vee F_ 2\left \rceil \right. \!\! F_ 3\vee F_ 3$;

4) Удалить член $( F_ 1\vee \left \rceil \right. \!\! F_ 1)$, так как $( F_ 1\vee \left \rceil \right. \!\! F_ 1)=и$:

$F =\left \rceil \right. \!\! F_ 2\vee F_ 2\left \rceil \right. \!\! F_ 3\vee F_ 3$;

5) Выполнить преобразование по закону дистрибутивности:

$F =\left \rceil \right. \!\! F_ 2\vee (F_ 2\vee F_ 3) (\left \rceil \right. \!\! F_ 3\vee F_ 3);$

6) Удалить член $( F_ 3\vee \left \rceil \right. \!\! F_ 3)=и$:

$F =\left \rceil \right. \!\! F_ 2\vee (F_ 2\vee F_ 3);$

7) Применить закон ассоциативности:

$F =(\left \rceil \right. \!\! F_ 2\vee F_ 2)\vee F_ 3;$

7) Приравнять “истине” значение формулы $F , т.к. (\left \rceil \right. \!\! F_ 2\vee F_ 2)=и:$

$$F=и\vee F_ 3=и.$$

 

Пример 2: Дано $F =\left \rceil \right. \!\! (F_ 1\rightarrow F_ 2)(\left \rceil \right. \!\! F_ 3\vee \left \rceil \right. \!\! F_ 4)\vee \left \rceil \right. \!\! (F_ 1\vee F_ 2)\left \rceil \right. \!\! (F_ 3F_ 4).$

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

Решение.

1) Удалить логическую связку $“\rightarrow ”$:

$F=\left \rceil \right. \!\! (\left \rceil \right. \!\! F_ 1\vee F_ 2)(\left \rceil \right. \!\! F_ 3\vee \left \rceil \right. \!\! F_ 4)\vee \left \rceil \right. \!\! (F_ 1\vee F_ 2)\left \rceil \right. \!\! (F_ 3F_ 4);$

2) Опустить отрицание на элементарные формулы по закону де Моргана:

$F =F_ 1\left \rceil \right. \!\! F_ 2(\left \rceil \right. \!\! F_ 3\vee \left \rceil \right. \!\! F_ 4)\vee \left \rceil \right. \!\! F_ 1\left \rceil \right. \!\! F_ 2(\left \rceil \right. \!\! F_ 3\vee \left \rceil \right. \!\! F_ 4);$

3) Выполнить преобразование по закону дистрибутивности:

$F =( F_ 1\vee \left \rceil \right. \!\! F_ 1) \left \rceil \right. \!\! F_ 2(\left \rceil \right. \!\! F_ 3\vee \left \rceil \right. \!\! F_ 4);$

4) Удалить член $( F_ 1\vee \left \rceil \right. \!\! F_ 1)=и:$

$F =\left \rceil \right. \!\! F_ 2(\left \rceil \right. \!\! F_ 3\vee \left \rceil \right. \!\! F_ 4).$

Дальнейшее упрощение формулы $F$ невозможно.