Примеры формализации высказываний естественного языка с помощью формул алгебры высказываний

Формулы логики высказываний

Лекция 2. Истинностные функции логики высказываний

ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

Истинностные значения и истинностные таблицы формул логики высказываний

Отношение равносильности формул

Истинностные функции

Совершенные нормальные формы истинностных функций

Полные системы истинностных функций

Классификация формул логики высказываний

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

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

Основные символы языка логики высказываний:

1. Пропозициональные переменные А, В, С,...,А₁, В₁,..., С₅,... – буквы латинского алфавита (атомы), которые используются для простых высказываний.

2. Логические связки Ø, Ú, Ù, Þ, Û.

3. Круглые скобки ().

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

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

1. Любая пропозициональная переменная является пропозициональной формулой.

2. Если А - пропозициональная формула, то (АÙВ), (АÚВ), (АÞВ), (АÛВ), (¬А) также является пропозициональной формулой.

3. Других формул, кроме как полученных из п.1-2, нет.

Пример: СÞАÚВ - пропозициональная формула; ÞАùВ - не является пропозициональной формулой.

Пример. Возьмем выражение (АÙВ) Þ (СÚА). Покажем, что оно является формулой алгебры высказываний.

Доказательство: А,В,С – логические переменные, которые являются формулами алгебры высказываний (из 1 пункта определения); (АÙВ) и (СÚА) тоже являются формулами по 2 пункту определения.

(АÙВ) Þ (СÚА) тоже является формулами алгебры высказываний по 2 пункту определения. Обозначим АÙВ =a, СÚА =b получим a Þ b, которая является пропозициональной формулой.

1. Если число 96 делится на 6, то оно делится на 3.

Обозначим через А высказывание: «96делится на 6», а через В – «96 делится на 3».

Тогда сложное высказывание запишем так: А Þ В.

2. Число 25 делится на 5, но не делится на 3. Обозначим через А высказывание:

«25 делится на 5», а через В – «25 делится на 3». Тогда запишем так: АÙ¬ùВ.

Истинностные значения и истинностные таблицы формул логики высказываний

Пусть формула А содержит п атомов P₁,..., Р_п. Так как каждый атом может принимать одно из двух возможных истинностных значений И или Л, то различных возможных наборов значений п атомов P₁,..., Р_п имеется 2ⁿ.