Лекция № 2. Основные вопросы, рассматриваемые на лекции

Тема: ПРОПОЗИЦИНАЛЬНЫЕ ФОРМУЛЫ

Основные вопросы, рассматриваемые на лекции:

1. Алфавит пропозициональной логики

2. Формулы логики высказываний (пропозициональные формулы)

3. Тавтологии. Противоречия

4. Логические следствия

Краткое содержание лекционного материала

Напомним, что алфавит – это конечное непустое множество символов.

Слово (или строка) в алфавите U – это конечная последовательность символов из U.

Пропозициональные переменные p, q, r, p ₁, p ₂, …– это переменные, значениями которых являются высказывания.

Рассмотрим слова в алфавите, состоящем из пропозициональных символов, логических связок Ø, Ú, Ù, Þ, Û и скобок. Среди них выделим пропозициональные формулы, для краткости называемые формулами:

1) каждая пропозициональная переменная является формулой;

2) если слово A – формула, то слово Ø A тоже формула;

3) если слова A и B – формулы, то слова (A Ú B), (A Ù B), (A Þ B) и (A Û B) тоже формулы;

4) только те слова являются формулами, которые получены строго по правилам пунктов 1) – 3).

В построенных формулах внешние скобки опускаются.

Предположим, что в состав формулы A входят пропозициональные переменные p ₁,…, p_n. Формула A называется тавтологией (противоречием), если при любых истинностных значениях переменных p ₁,…, p_n формула A всегда принимает истинностное значение 1 (соответственно, 0).

Если формула A принимает истинностное значение 1 (0), мы говорим, что формула A истинна (ложна) и пишем A º1 (A º0).

Предположим, что в состав формул A ₁,…, A_m, B входят пропозициональные переменные p ₁,…, p_n. Говорят, что формула B логически следует из формул A ₁,…, A_m (или B – логическое следствие A ₁,…, A_m), если при любых истинностных значениях переменных p ₁,…, p_n как только формулы A ₁,…, A_m становятся истинными, так и формула B становится истинной, или, что равносильно, формула A ₁Þ(A ₂Þ…Þ(A_m Þ B)…) является тавтологией.

В частности, B логически следует из A (из A ₁ и A ₂), если формула A Þ B (соответственно, A ₁Þ(A ₂Þ B)) является тавтологией.

Логическое следствие – это отношения между высказываниями. Знаки Þ (и ему подобные знаки ®, É) на практике применяются и для обозначения операций над высказываниями (импликация A Þ B), и для отношений между высказываниями (логическое следствие), и для краткой записи в доказательствах последовательного выполнения отношений логического следствия.

Логические следствия применяются при доказательстве теорем.

Примеры различных логических следствий, используемых при доказательстве методом от противного:

1) из Ø A Þ B и Ø A ÞØ B следует A;

2) из Ø A Þ A следует A;

3) из Ø A Þ(B ÙØ B) следует A;

4) из Ø A Þ0 следует A.

Следующее логическое следствие называется правилом силлогизма:

5) из A Þ B и B Þ C следует A Þ C.

Правило отделения или modus ponens:

6) из A и A Þ B следует B.