Основні правила одержання тавтологій

Теорема 2.2 (правило висновку). Якщо формули F і F Н є тавтологіями, то формула Н також є тавтологією. Іншими словами, із ╞ F і ╞ F H випливає ╞ H.

Доведення. Нехай ╞ F (,..., „) і ╞ F (,..., „) H (,..., ). Покладемо, що формула H (,..., ) не є тавтологією. Це означає, що існують такі конкретні висловлення ,..., , що . Оскільки F (,..., ) - тавтологія, то для ,..., , маємо . Далі маємо:

,

що суперечить тотожній істинності формули F Н. Отже, припущення, що H (,..., ) не є тавтологією неправильне. Звідси одержуємо: ╞ Н, що й потрібно було довести.

Правило висновку називається також правилом “модус поненс”

Друге правило одержання тавтологій має назву правила підстановки. Нехай у формулі F міститься пропозиційна змінна X, і H - довільна формула. Якщо в формулу F замість символу X всюди, де вона входить в F, вставити формулу Н, то одержимо нову формулу. Вона позначається й називається формулою, одержаною з F в результаті підстановки в неї формули Н замість пропозиційної змінної X. Наприклад, якщо в формулу замість змінної Y підставити формулу (), то одержимо .

Теорема 2.3 (правило підстановки). Якщо формула F, що містить пропозиційну змінну X, є тавтологією, то підстановка в формулу F замість змінної X будь-якої формули Н знову приводить до тавтології. Іншими словами, із ╞ F випливає ╞ .

Доведення безпосередньо випливає із означення тавтології. Так як ╞ F(X,Y,...), то формула F(Х, Y,...) перетворюється в істинне висловлення при підстановці замість всіх пропозиційних змінних X, Y,... довільних конкретних висловлень. Істинність одержуваного висловлення не залежить від структури висловлень, які підставляються заміст змінних X, Y,....

Зауваження. Кожна із пропозиційних змінних у даних формулах може розглядатися не як змінна, а як довільна формула алгебри висловлень. Наприклад, тавтологія виду ╞ , де - довільні формули алгебри висловлень.

Розглянуті два правила утворення тавтологій будемо називати основними.