Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Формальная логика.doc
Скачиваний:
7
Добавлен:
01.07.2025
Размер:
6 Мб
Скачать
☆

§ 5. Равносильные формулы

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

столбцов.

Например, в таблицах формул (р-> ~q) и ~(pVq)

р

Я

~ Я

(р -> ~ q)

р

я

iPAq)

~ (рАя)

и

и

л

-л

и

и

и

л

л

и

л

и

л

и

л

и

и

л

и

и

и

л

л

и

л

л

и

и

л

л

is

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

Определение. Пусть А и В — формулы, Е[, Ег, Е„ список всех пропозициональных переменных, входящих по край­ней мере в одну из них. Будем говорить, что А и В — равносиль­ные формулы (и писать: А равносильно В), если при любых ло­гических значениях Еь Ег, Е„ логические значения А и В совпадают.

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

(~Р A(p-*q)) и (р-»(~рЛг)).

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

р

я

г

~ р

(р-*ч)

(~/>Л (р-*■</))

и

и

,

л.

и

я

л

н

и

и

и

и

и

л

и

л

л

л

л

л

и

и

и

и

и

и

л

л

и

л

л

и

л

и

и

и

и

л

л

л

л

л

л

л

'

! "

и

и

р

<г

г

~р

(~рЛг)

(р-*(~ рЛг))

и

и

и

л

л

л

л

и

и

и

и

и

и

л

и

л

л

л

л

л

и

и

и

и

и

и

л

л

л

л

л

и

л

■

л

и

и

л

л

л

л

л

л

л

л

и

л

и

Из таблиц видно, что данные формулы равносильны.

Говорят, что логические значения формулы А не зависят от пропозициональной переменной Е,-, если для любого набора ло­гических значений остальных пропозициональных переменных в таблице формулы А логическое значение А одно и то же, когда Е4 истинно и когда Е< ложно. Видно, что логические зна­чения обеих формул не зависят ни от переменной г, ни от пере* менной <7,

Отношение равносильности, во-первых, рефлексивно, т. е. А равносильно А; во-вторых, симметрично, т. е. если А равно­сильно В, то В равносильно А, и, в-третьих, транзитивно, т. е. если А равносильно В и В равносильно С, то А равносильно С.

Два высказывания называются равнозначными, если они могут быть получены из равносильных формул А и В в ре­зультате замены всех входящих в них переменных конкретными высказываниями.

Например, высказывание Если студент плохо знает пред­мет, то он не сдаст экзамен равнозначно высказыванию Не­верно, что студент плохо знает предмет и он сдаст экзамен, так как их можно получить из формул (р-> ~<7) и ~ (р Aq), при­давая переменным р и q значения Студент плохо знает предмет и Он сдаст экзамен.

Рассмотрим некоторые равносильные формулы, условившись в дальнейшем во всех формулах для упрощения записи опу­скать внешние скобки.

Пусть А любая формула, тогда

~ ~ А равносильно А. (О

Эта равносильность означает, что двойное отрицание любой формулы равносильно самой этой формуле: формула ~~А истинна, когда истинна формула А, и ложна, когда А ложна. В этом легко убедиться, построив таблицу, во входном столбце которой выписаны логические значения формулы А, а в заклю­чительном — формулы ~ ~ А.

А

~А

~ ~ А

и

л

и

л

и

л

Равносильность всех приводимых ниже схем формул также может быть обоснована построением соответствующих таблиц. Таблицы для схем формул строятся аналогично таблицам для формул, с той лишь разницей, что везде вместо пропозицио­нальных переменных р, q, г, s, ... стоят буквы А, В, С, D, ... Фактическое построение таких таблиц предоставляется чи­тателю.

Пусть А, В, С любые формулы, тогда

АЛВ равносильно В Л А; (2)

А Л (В Л С) равносильно (А Л В) Л С. (3)

Равносильности (2) и (3) свидетельствуют о коммутатив­ности и ассоциативности конъюнкции. Учитывая равносильность

(3), условимся в дальнейшем употреблять бесскобочную за­пись А Л В Л С. Равносильности

А V В равносильно В V А; (4)

А V (В V С) равносильно (А V В) V С (5)

свидетельствуют о коммутативности и ассоциативности дизъюнк­ции. Учитывая (5), условимся в дальнейшем употреблять бес-

скобочную запись А V В V С. Следующие равносильности:

AV(BAC) равносильно (А V В) Л (А V С); (6)

(В Л С) V А равносильно (А V В) Л (А V С); (6')

AA(BVC) равносильно (А Л В) V (А Л С); (7)

(BVC)AA равносильно (А Л В) V (А Л С) (7')

свидетельствуют о дистрибутивности дизъюнкции относительно конъюнкции и дистрибутивности конъюнкции относительно дизъюнкции.

Проиллюстрируем равносильность (7). Высказывание о по­годе за какой-то период Стояли морозные дни, и в то же время был сильный снегопад или дул резкий ветер, которое имеет вид АЛ(ВЛ^С), равнозначно высказыванию Стояли морозные дни, и был сильный снегопад, или же стояли морозные дни, и дул резкий ветер, которое имеет вид (АЛ В) V (А Л С).

Следующие две равносильности:

АЛА равносильно А; (8)

А V А равносильно А (9)

называются законами идемпотентности конъюнк­ции и дизъюнкции. Равносильности

~(АЛВ) равносильно ~А V ~В; (10)

~ (А V В) равносильно ~ А Л ~В (11)

называются законами п.е Моргана.

Примером (10) является равнозначность высказывания Не­верно, что данный треугольник прямоугольный и что он в то же время равнобедренный высказыванию Или этот треугольник не прямоугольный, или он не равнобедренный. Заметим, что так как дизъюнкция здесь не исключающая, то может быть, что этот треугольник и не прямоугольный, и не равнобедренный.

Примером (11) может служить равнозначность высказыва­ния Неверно, что или он изучал логику в школе, или он про­слушал курс логики в вузе высказыванию Он не изучал логику в школе и он не слушал курса логики в вузе.

Рассмотрим еще ряд равносильностей.

АДВ равносильно ~(А-*~В) (12)

Например, высказывание Летом он поедет в Ленинград и посетит «Эрмитаж-» равнозначно высказыванию Неверно, что если летом он поедет в Ленинград, то не посетит «Эрмитаж-».

А-*В равносильно ~А VB. (13)

Например, высказывание Если взялся за дело, то доведи его до конца равнозначно высказыванию Или не берись за дело, или доведи его до конца.

АДВ равносильно ~(~А V ~В). (14)

Например, высказывание У квадрата стороны равны и углы прямые равнозначно высказыванию Неверно, что у квадрата стороны не равны или углы не прямые.

A VB равносильно ~(~АД ~В). (15)

Например, высказывание Данный треугольник или равносто­ронний или равнобедренный равнозначно высказыванию Не­верно, что данный треугольник не равносторонний и не равно­бедренный.

Нам понадобятся в дальнейшем также равносильности

А-*-*В равносильно (~ А V В) Л (~ В V А); (16) А<*В равносильно (А V В) Л (~ А V ~ В); (17) (А V В)ЧЛ (~ А V В) равносильно В; (18)

А Л (А V В) равносильно А; (19)

А V (А Л В) равносильно А; (20)

(AVC)A(BV~C) равносильно (AVC)A(BV~C)A(AVB); (21) (AAC)V(BA~C) равносильно (AAC)V(BA~C)V(AAB). (22)

Равносильность (18) называется законом исключения, равносильности (19) и (20) — законами поглощения, а равносильности (21) и (22) — законами выявления.

Каждое из соотношений (1) — (22) содержит схемы формул и относится к бесконечному множеству равносильных друг другу формул логики высказываний соответствующего вида.

Например, равносильность (13) относится к следующим па­рам конкретных формул:

p-*q и ~ рУ q; ~p->~q и ~ ~ р V ~

р—>-р и ~pVp; ~ q —> ~ q и ~ ~ ? V ~ ?;

(~Р Л q)-*(r V ~s) и ~(~р Aq)V(r V ~s);

({p->q)^r)-*s и ~{{p->q)->r) Vs и т. д.

Упражнения.