Elementy_mat_logiki_Teoria

Теория

Высказывания (основные понятия)

Введем специфическую «логическую» терминологию и укажем её связь с положениями раздела «Элементы математической логики. Алгебра булевых функций».

Определение.

Высказывание – это утверждение или повествовательное предложение, о котором можно сказать, истинно оно или ложно, но ни то и другое одновременно.

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

Пример.

Предложения, являющиеся высказываниями:

а) Два умножить на два равно четыре ( 2 2 4 ). б) Рим − столица Франции.

Предложения, не являющиеся высказываниями: а) Кто Вы? (вопрос).

б) Прочтите эту книгу до следующего занятия (приказ или восклицание). в) Это утверждение ложно (внутренне противоречивое утверждение).

Определение.

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

(элементарными высказываниями, атомарными формулами).

Высказывание можно рассматривать как величину, (пропозициональную переменную, высказывательную переменную), которая может принимать два значения: «истина» и «ложь», т.е. принимать истинностное значение.

Определение.

Под истинностным значением понимается абстрактный объект («истина» или «ложь»), сопоставляемый высказыванию в зависимости от того, является это высказывание истинным или ложным. Обозначается: «истина» − И, Т (True) или 1, „ложь” – Л, F (False) или 0.

Определение.

Множество {И, Л} называется множеством истинностных значений.

Пример.

Высказывание « 2 2 4 » имеет истинностное значение 1 (И).

Высказывание «Рим − столица Франции» имеет истинностное значение 0 (Л).

Можно рассматривать две группы высказываний:

высказывания, истинностное значение которых независимо от ситуации можно считать однозначно определенным;

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

Обычно эти обстоятельства не фигурируют явно в простом высказывании.

Пример.

а) Высказывание « 5 5 25 » определено однозначно.

б) Истинность таких высказываний, как «Хорошая погода», «Сегодня 31 декабря», «Результат измерений диаметра цилиндра равен 52 мм» зависит, соответственно, от вкусов или критерия оценки погоды, сегодняшней даты, требуемой точности измерения. Высказывание «Завтра будет дождь» может получить значение «истина» или «ложь» в зависимости от конкретной ситуации.

В качестве символов для обозначения атомов используются заглавные буквы латинского алфавита A, B, C, ... или заглавные буквы с индексами. Каждая буква в

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

Пример.

а) A «Снег белый».

б) A1 «Аня является студенткой университета».

в) X − «Группа КН-11-1 насчитывает 19 студентов».

Логические связки и формулы логики высказываний

Рассматривая конструкции естественного языка, видим, что простые предложения объединяются в сложные при помощи соответствующих сентенциональных связок (союзов), т.е. сложные предложения состоят из простых предложений и служебных слов («если», «то», «и», «или» и т.п.).

Пример.

Составные (сложные) высказывания:

а) «Снег белый, и температура ниже нуля». б) «Если Петр на занятиях, то Аня дома». в) «Петр − студент института или шахтер».

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

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

Из одних высказываний различными способами можно строить новые, более сложные высказывания, называемые формулами или молекулами, используя те же операции (и их символы), что и в булевой алгебре. Примеры связок и их символов приведены в таблице 4.1.

Таблица 4.1 − Логические связки в логике высказываний

Название	Обозначение				Аналоги естественного языка
Отрицание					не, «неверно, что»
	,
Конъюнкция	,			&	и
Дизъюнкция					или, «или одно из двух …, или
					оба», либо
Импликация	,				влечет, «если, …то», «только
					если», «только тогда, когда», «есть
					достаточное условие», «при
					условии, что», «есть необходимое
					условие»
Эквивалентность	~ , ,				эквивалентно, равносильно, «тогда
					и только тогда, когда», «если и
					только если», «есть необходимое и
					достаточное условие»

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

Определение.

Отрицанием высказывания A называется высказывание (обозначение A ), которое истинно тогда и только тогда, когда A ложно.

Данная унарная операция соответствует отрицанию в естественном языке, которое может иметь различные синтаксические выражения (см. таблицу 4.1).

Пример.

Пусть имеем высказывание A − «Владимир получил электронное письмо от Александра». Отрицанием высказывания A является: A − «Владимир не получил электронное письмо от Александра». Данное высказывание можно представить следующим образом: A − «Неверно, что Владимир получил электронное письмо от Александра».

Определение.

Высказывание A B , называемое конъюнкцией A и B , истинно тогда и только тогда, когда истинны оба высказывания A и B .

Эта логическая операция соответствует в естественном языке связке «и», соединяющей два предложения.

Пример.

Пусть имеем простые высказывания: A − «Харьков является первой столицей Украины»; B − «Харьков − красивый город».

Составное высказывание, определяющее конъюнкцию, будет иметь вид: A B − «Харьков является первой столицей Украины и Харьков − красивый город».

Определение.

Высказывание A B , называемое дизъюнкцией A и B , ложно тогда и только тогда, когда ложны оба высказывания A и B .

Эта логическая операция соответствует соединению высказываний естественного языка с помощью связки «или», употребляемой в смысле «не исключающее или»: «верно» A , или верно B , или оба высказывания равны.

Пример.
Пусть имеем два атома: A − « 5 2 10» и		B − « 5 2 10 ». Тогда
высказывание «5 2 10 или	5 2 10 » будет соответствовать формуле A B .
Определение.
Высказывание A B ,	называемое импликацией (условным предложением),
ложно тогда и только тогда, когда A истинно, а B ложно.
В импликации A B	высказывание A называется посылкой (условием,
антецедентом), а B следствием (заключением, консеквентом). Выражаемая
импликацией причинно-следственная связь между A и		B на естественном языке

описывается следующими оборотами: « A влечет B », «если A , то B », « A является достаточным основанием для B », « B , потому что A », « B при условии выполнения A ». Используемые в точных науках понятия достаточного и необходимого условий можно формально выразить с помощью импликации.

Пример.

Пусть имеем два атома: A − « x − простое» и B − « x − нечетное». Тогда высказывание «Для того, чтобы x было нечетным, достаточно, чтобы x было простым» будет соответствовать формуле A B .

Определение.

Если A и B высказывания, то высказывание A ~ B , называемое эквиваленцией, истинно тогда и только тогда, когда A и B либо оба истинны, либо оба ложны.

Эта операция в естественном языке соответствует оборотам: «… тогда и только тогда, когда …», «для того чтобы …, необходимо и достаточно …»,

Пример.

Пусть имеем два атома: A − «идет дождь» и B − «на небе тучи». Тогда высказывание «Дождь идет тогда и только тогда, когда на небе тучи» будет соответствовать формуле A ~ B .

Алфавит логики высказываний содержит следующие символы:

1)высказывательные переменные A, B, C, ... или заглавные буквы с

индексами;

2)логические символы (связки) , , , , ~ ;

3)символы скобок ( ) и запятую.

Связки могут быть бинарными и унарными. Операции , , , ~ являются

бинарными логическими связками, операция − унарной логической связкой.

При записи формул можно обойтись без некоторых скобок, если приписать ранги логическим связкам. Ранги логических связок чаще всего задаются в таком порядке (от высшего к низшему): , , , , ~ .

Пример.

P − «Влажность большая».

Q − «Температура высокая».

C − 2Мы чувствуем себя хорошо».

Высказывание «Если влажность большая и температура высокая, то мы не чувствуем себя хорошо» можно записать в виде формулы ((P Q) ( C)) или с

учетом рангов операций P Q C .

Определение.

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

1.Атом есть формула.

2.Если A и B формулы, то (A B), (A B), (A B), (A ~ B), A также

формулы.

3. Никаких формул, кроме порожденных указанными выше правилами, не существует.

Алгебра логики и логика высказываний

Определение.

Логика высказываний – это алгебраическая структура ({Л, И}, , , , , ~,) )

с носителем – двоичным множеством { Л : «Ложь», И : «Истина»}, операциями (логическими связками): « » – конъюнкция, « » – дизъюнкция, « » – отрицание, « » – импликация, «~» – эквивалентность.

Если рассмотреть две алгебры: алгебру логики A1 ({0,1}, , , , , ~) и алгебру логики высказываний A2 ({Л, И}, , , , , ~) , то они будут изоморфны

друг другу, так как можно поставить взаимно однозначное соответствие между множествами 0 Л , 1 И , а операции просто одинаковы. Если алгебры изоморфны, то элементы и операции A2 можно переименовать так, что A2 совпадает

с A1 . Из условия изоморфности следует, что любое эквивалентное соответствие в

алгебре A1 сохраняется в A2 . То есть соотношения, полученные в алгебре A1 , автоматически распространяются на алгебру A2 .

С логической точки зрения двоичные объекты, которые рассматривались в разделе «Элементы математической логики. Алгебра булевых функций», это высказывания, которые могут быть истинными или ложными. Формулы это составные высказывания, истинность которых определяется истинностью входящих в них элементарных высказываний (обозначаемых буквами) и логическими операциями над высказываниями.

Поэтому все утверждения относительно алгебры логики справедливы и для алгебры логики высказываний.

Если рассматривать формулы, содержащие только логические операции, , , то в логике высказываний выполняется закон двойственности. Кроме того,

формулы логики высказываний можно представить в виде ДНФ и КНФ, СДНФ и СКНФ (учитывая изоморфизм алгебр).

Интерпретация формул логики высказываний. Правильные рассуждения

Определение.

Приписывание истинностных значений атомам, из которых построено высказывание, называется интерпретацией высказывания.

Для высказывания, содержащего n атомов, можно составить 2n интерпретаций, так же, как и для n -местной булевой функции.

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

Пример.

Рассмотрим таблицу истинности для логических связок логики высказываний (таблица 4.2)

Таблица 4.2 Таблица истинности логических связок

A	B				A B	A B	A B	A ~ B
			A
Л	Л	И			Л	Л	И	И
Л	И	И			Л	И	И	Л
И	Л	Л			Л	И	Л	Л
И	И	Л			И	И	И	И

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

Определение.

Формула называется тождественно истинной (тавтологией или

общезначимой), если она принимает значение «истина» на всех интерпретациях (наборах значений переменных).

Определение.

Формула называется тождественно ложной (противоречивой или

невыполнимой), если она принимает значение «ложь» на всех интерпретациях.

Определение.

Формула называется необщезначимой или непротиворечивой, если она на одних интерпретациях принимает значение «истина», а на других – «ложь».

Определение.

Все формулы, не относящиеся к противоречивым, образуют множество

выполнимых формул.

Пример.

Формула A A − тавтология; формула A A является противоречивой; формула A A является выполнимой.

Перечислим наиболее важные тавтологии, предполагая, что A, B,C − произвольные формулы:

1.A A ;

2.A A ;

3.A (B A) ;

4.(A B) ((B C) (A C));

5.(A (B C)) ((A B) (A C)) ;

6. (A B) A,		(A B) B ;
7.	A (B (A B)) ;
8.	A (A B),	B (A B) ;

9.( B A) (( B A) B) ;

10.((A B) A) A (закон Пирса).

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

Определение.

Рассуждение называется правильным, если оно выражается тождественно истинной формулой.

Таким образом, проверить правильность рассуждения можно, построив соответствующую ему формулу и определив, является ли она тождественно истинной.

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

1.Построить таблицу истинности этой формулы. Если в таблице истинности на всех интерпретациях функция принимает значение «истина», то соответствующее формуле рассуждение является тавтологией.

2.Применив тождественные преобразования, привести её к виду одного из логических законов. Если в результате преобразований получим значение «истина», то формула является тавтологией.

Логическая эквивалентность и логическое следствие

Определение.

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

Равносильность формул логики высказываний вытекает из тождественности соответствующих формул алгебры логики. Равносильности формул A и B будем обозначать через A B . Легко видеть, что равносильность − это отношение эквивалентности (оно рефлексивно, симметрично и транзитивно), поэтому равносильность называют также логической эквивалентностью.

Теорема.

Если A, B,C − любые формулы, то имеют место следующие логические эквивалентности:

1.A B B A, A B B A (коммутативность).

2.A (B C) (A B) C , A (B C) (A B) C (ассоциативность).

3.A (B C) (A B) (A C) ,

A (B C) (A B) (A C) (дистирибутивность).

4.A A A, A A A (идемпотентность).

5.A ( A B) A , A (A B) A (законы поглощения).

6.A A (закон двойного отрицания.)

7.(A B) A B , (A B) A B (законы де Моргана).

8.A Л А, A Л Л .

9.A И И , A И А.

10.A А И , A А Л .

Кроме того, с помощью отношения равносильности выражаются различные

связки между

формулами:

A B A B ,

A ~ B AB AB (A B)(A B) ,

A B A B ,

AB A B ,

A ~ B (A B)(B A) ,

A (A B) (A B) ,

A (A B) (A B) .

Любая из равносильностей может быть доказана с помощью таблиц истинности (а также следует из изоморфизма алгебр A1 и A2 ).

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

Определение.

Высказывание B является логическим следствием высказывания A , если формула A B является тождественно истинной.

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

Определение.

Высказывание B является логическим следствием высказываний A1 , A2 ,..., An , если A1 A2 ... An B − тождественно истинная формула.

Пример.

Показать, что высказывание ( A B) C является логическим следованием

высказывания A C .

Покажем, что формула (A C) (A B) C является общезначимой. Для этого используем тождества логики высказываний для эквивалентных

преобразований, учитывая, что x y f13 (x, y) x y :

(A C) (A B) C (A C) (A B) C A C (A B) CA (A B) C C A (A B) И И .

Общезначимость формулы доказана.

Исчисление высказываний

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

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

Исчисление высказываний содержит язык, систему аксиом и правила вывода.

Рассмотрим каждое из этих составляющих.

Определение.

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

Пример.

Правильно построенные формулы с использованием алфавита логики высказываний: (A (B (C D))) , ((A (A B)) ((C D) (A B))).

Выражения, не являющиеся формулами: ( A B , A B , A.

Аксиомы и полнота исчисления логики высказываний

В математике и «чистой» логике доказывают теоремы, т.е. выводят следствия из определенных допущений, которые называются аксиомами или гипотезами. При этом предполагается, что они (аксиомы или гипотезы) тождественно истинны во всей рассматриваемой теории.

Определение.

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

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

Системы аксиом исчисления высказываний подбираются таким образом, чтобы исчисление обладало свойством полноты.

Полнота исчисления высказываний заключается в том, что в данной системе имеется достаточное количество аксиом для того, чтобы вывести любую формулу логики высказываний, которая является тождественно истинной.

Выводимость в исчислении высказываний

Определение.

Выводом в исчислении высказывания называется всякая последовательность A1 , A2 ,..., An формул такая, что для любого i формула Ai есть либо аксиома,

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

Определение.

Формула A называется теоремой исчисления высказывания (как аксиоматической теории), если в ней существует вывод, в котором последней формулой является A . Этот вывод называется выводом формулы A .

Определение.

Формула A называется следствием множества формул G тогда и только тогда, когда существует такая последовательность формул A1 , A2 ,..., An , что An есть

A , и для любого i формула Ai есть либо аксиома, либо формула из G , либо

непосредственное следование некоторых предыдущих формул. Эта последовательность называется выводом A из G . Элементы G называются

посылками вывода или гипотезами.

Сокращенно можно записать так: G A ( A есть следствие G ). Если множество G состоит из формул B1 , B2 ,...,Bk , то пишут B1 , B2 ,...,Bk A.