Логічний наслідок і рівносильність формул

Дві властивості логічного наслідку.

Теорема 5.3. Відношення логічного наслідку між формулами алгебри висловлень має наступні властивості:

а) ╞ ,для i = 1, 2, …, т (рефлексивністьвідношення логічного наслідку);

б) якщо ╞ для j = 1, 2, …, р і ╞ , то ╞ (транзитивність відношення логічного наслідку).

Логічний наслідок і рівносильність формул.

Теорема 5.4. Дві формули алгебри висловлень рівносильні тоді й тільки тоді, коли кожна із них є логічним наслідком іншої: F @ H Û H @ F.

Наслідок. Якщо деяка формула є тавтологією, то і будь-який її логічний наслідок також є тавтологією. Символічно це можна записати так: ╞ F, F ╞ H Þ ╞ H.

Доведення. Необхідність. Дано: . За означенням рівносильності обидві формули і для довільних конкретних висловлень перетворюються в висловлення і , які одночасно або істинні або хибні. Отже, кожне із висловлень → і → істинне для будь-яких висловлень . Це означає, що ╞ → і ╞ → , звідки й випливає ╞ і ╞ .

Достатність. Дано: ╞ і ╞ . Тоді ╞ → і ╞ → . Оскільки формули → й → завжди перетворюються в істинні висловлення, то і їх кон’юнкція ( → ) ( → ) є формулою, яка завжди перетворюється істинне висловлення, тобто ╞ ( → ) ( → ). Але ( → ) ( → ) ↔ . Отже ╞ ↔ , а значить .

Наслідок. Якщо деяка формула є тавтологією, то і будь-який її логічний наслідок також є тавтологією. Символічно це можна записати так: ╞ F, F ╞ H Þ ╞ H.