Лекция 2. Алгебра высказываний

Напомним основные сведения о высказываниях и логических опера-

циях над ними, рассмотренные во вводном курсе математики. Высказы-

вание в математике—это повествовательное предложение, относительно

которого можно сказать истинно оно или ложно.

Рассмотрим следующие предложения.

1. Число 6 является четным числом.

2. Екатеринбург—город в Европе.

3. Какое сегодня число?

4. x > 3.

Первое предложение является высказыванием, причем истинным. Вто-

рое предложение также высказывание, но ложное. Относительно пред-

ложений 3 и 4 нельзя сказать, истинны они или ложны. Поэтому они не

является высказываниями.

Высказывание будем обозначать латинскими буквами. Рассмотрим

логические знаки

∧, ∨, →, ↔, ￢,

с помощью которых из высказываний A и B можно составлять следую-

щие сложные высказывания:

A ∧ B —читается «A и B » или « A конъюнкция B»;

A ∨ B – читается « A или B» или «A дизъюнкция B»;

A → B —читается « A влечет B» или «A импликация B»;

A ↔ B — читается «A тогда и только тогда, когда B» или «A эквива-

лентно B»;

￢A—читается «не A».

Правила приписывания этим сложным высказываниям значения «ис-

тина» или «ложь» следующие.

• Высказывание A ∧ B является истинным тогда и только тогда, когда

истинны оба высказывания A и B.

• Высказывание A ∨ B истинно тогда и только тогда, когда истинно

хотя бы одно из высказываний A и B.

• ВысказываниеA → B ложно только в одном случае, когда высказы-

вание A истинно, а B — ложно, в остальных случаях высказывание

A → B истинно.

• Высказывание A ↔ B истинно тогда и только тогда, когда A и B оба

истинны или оба ложны.

• Высказывание ￢A имеет значение истинности, противоположное

значению истинности для A.

Эти определения отражены в следующих таблицах истинности. В них

высказываниям A и B придаются значения Иили Л ( истина или ложь) и

приводится значение составного высказывания.

A B A ∧ B A ∨ B A → B A ↔ B

И И И И И И

И Л Л И Л Л

Л И Л И И Л

Л Л Л Л И И

A ￢A

И Л

Л И

Таким образом можно составить таблицу истинности для произволь-

ной формулы. Напомним определение тождественно истинной формулы (

тавтологии ).

ОПРЕДЕЛЕНИЕ 1 Формула A называется тождественно ис-

тинной формулой, если при подстановке значений И (истина) или

Л (ложь) в качестве значений входящих в формулу букв, значение

формулы A всегда равно И.

Тождественно истинные формулы—это законы логики. Существуют две

причины, по которым мы считаем какое-либо суждение истинным. Рас-

смотрим, например, предложение «Екатеринбург—город в Европе».Мы

объявляем это высказывание ложным. Значение «ложь» приписывается

исходя из свойств обсуждаемых объектов. Точно также в случае выска-

зывания «2·3 = 6» значение «истина» установлено из свойств объектов 2

и 3.Однако существует случаи, когда приписывание предложению значе-

ние «истина» или «ложь» не учитывает свойств обсуждаемых объектов,

а имеет другую природу—логическую истинность.

Рассмотрим предложение «верно, что студент Иванов сдал зачет по

логике или он не сдал зачет». Любой человек может объявить, что это

утверждение истинно, даже не зная конкретной информации про Ивано-

ва. Почему это так? Мы понимаем, что имеем дело с предложением вида

￢A ∨ A, где A — «Иванов сдал зачет». Поскольку формула ￢A ∨ A яв-

ляется тождественно истинной, то независимо от значения A, значение

наше предложение истинно. Мы можем заменить предложение «Иванов

сдал зачет» на предложение «Екатеринбург — город в Европе», и снова

получим истинное высказывание ￢A ∨ A.

Можно постепенно обнаруживать все новые и новые законы логики,

подобные закону ￢A ∨ A, например,

￢￢A → A или (A → B) ↔ (￢A ∨ B).

Поэтому возникает вопрос, как получить достаточно простой способ

конструирования всех таких законов логики.Мы получим ответ в разделе

«Исчисление высказываний». В данный момент рассмотрим способ для

проверки тождественной истинности конкретных формул.

Лекция 3. Конъюнктивная и дизъюнктивная нормальные

формы

ОПРЕДЕЛЕНИЕ 2 Элементарной дизъюнкцией называется фор-

мула, являющаяся дизъюнкцией нескольких переменных X,Y,Z, . . .

или их отрицаний.

Пример. A = X ∨￢Y ∨ Z ∨ Y ∨￢X

ОПРЕДЕЛЕНИЕ 3 Элементарной конъюнкцией называет-

ся формула, являющаяся конъюнкцией нескольких переменных