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

Название логической связи	Обозначение логической связи	Союзы и обороты естественного языка
отрицание		«нет», «неверно, что», «неправда, что»
конъюнкция		«и»
дизъюнкция		«или», «или одно из них…или оба»
импликация		«если…, то», «только если», «тянет», «из того, что…следует…»
эквивалентность		«эквивалентно», «равносильно», «равнозначно», «тогда и только тогда», «если и только если»

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

АЛГЕБРА ВЫСКАЗЫВАНИЙ

Алгеброй высказываний называется множество , на котором определены логические операции отрицания, конъюнкции, дизъюнкции, импликации и эквивалентности.

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

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

Пример 1

Пусть высказывание «У Ивана есть время». Тогда высказывание можно представить такими повествовательными предложениями: «Не верно, что у Ивана есть время»; «Не правда, что у Ивана есть время»; «У Ивана нет времени». ∎

Конъюнкцией (логическим произведением) высказываний и называют высказывание , которое истинно, если оба высказывания и – истинны, и ложно, если хотя бы одно с них – ложное:

Эта логическая операция соответствует союзу «и» естественного языка: « и ».

Пример 2

Записатьформулой алгебры высказываний предложение естественного языка: «6 делится на 3 и 10 больше 5».

Выполнение. Введем атомы: : «6 делится на 3»; : «10 больше 5». Тогда заданное предложение естественного языка можно представить формулой алгебры высказываний . Так как и , то и , то есть высказывание «6 делится на 3 и 10 больше 5» – истинно.∎

Дизъюнкцией высказываний и называют высказывание , которое истинно, если хотя бы одно из высказываний или – истинно, и ложно, если оба высказывания – ложные:

Эта логическая операция соответствует союзу «или» естественного языка: « или ».

Пример 3

Записатьформулой алгебры высказываний повествовательное предложение естественного языка: «6 делится на 3 или 10 больше 15».

Выполнение. Введем атомы: : «6 делится на 3»; : «10 больше 15». Тогда заданное предложение естественного языка можно представить формулой алгебры высказываний . Так как и , то , то есть высказывание «6 делится на 3 или 10 больше 15» – истинно.∎

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

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

В импликации высказывание называется посылкой (условием), – заключением (выводом).

Пример 4

Высказывание «Если натуральное число 16 делится на 4, то оно четное» можно представить формулой , где атом Натуральное число 16 делится на 4», а атом : «Натуральное число 16 четное». Так как , , то , то есть высказывание «Если натуральное число 16 делится на 4, то оно четное» истинно.∎

Пример 5

Высказывание «Если натуральное число 32 делится на 8, то оно нечетное» можно представить формулой , где атом : «Натуральное число 32 делится на 8», а атом : «Натуральное число 32 нечетное». Так как , , то , то есть высказывание «Если натуральное число 32 делится на 8, то оно нечетное» ложно.∎

Пример 6

Высказывание «Если натуральное число 32 делится на 7, то оно четное» можно представить формулой , где атом : «Натуральное число 32 делится на 7», а атом : «Натуральное число 32 четное». Так как , , то , то есть высказывание «Если натуральное число 32 делится на 7, то оно четное» истинно.∎

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

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

Пример 2

Высказывание «Изучение информатики будет успешным тогда и только тогда, когда будет усвоена математическая логика» можно представить формулой , где атом : «Изучение информатики успешное», а атом : «Математическая логика усвоена».∎

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

· Атом – формула;

· Если и – формулы, то , , , , – также формулы;

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

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

Пример 2

.∎

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

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

· атомы алгебры высказываний соответствуют логическим переменным алгебры логики;

· истинностные значения высказываний F и T соответствуют логическим значениям 0 и 1;

· формулы алгебры высказываний соответствуют формулам алгебры логики;

· интерпретации высказывания алгебры высказываний соответствуют словам алгебры логики и т. д.

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

Пример 2

Задана формула алгебры высказываний

.

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

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

.

Вычисление по формуле.

1) ;

2) ;

3) ;

4) ;

5) ;

6) .

Ответ: .∎

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 1

Упражнение 1. Среди следующих предложений естественного языка выделить высказывания, определить, истинные они, или ложные.

1) Река Днепр впадает в Черное море.

2) Любой человек имеет брата.

3) Пейте томатный сок!

4) Ни один человек не весит больше 10000 кг.

5) Существует человек младше своего отца.

6) Где твоя чашка?

7) .

8) Для любых действительных чисел .

9) .

10)Любое действительное число .

11) .

12)При .

13)Не существует при котором .

Выполнение.

1) Да, это высказывание, оно истинно.

2) Да, высказывание ложно.

3) Нет, это восклицательное предложение.

4) Да, высказывание истинно.

5) Да, оно ложно.

6) Нет, это вопросительное предложение.

7) Да, высказывание ложное.

8) Да, высказывание истинно.

9) Да, высказывание ложно, .

10) Да, высказывание ложно.

11) Нет, не высказывание. Это алгебраическое выражение.

12) Да, высказывание истинно.

13) Да, высказывание истинно.

Упражнение 2. Записать формулами алгебры высказываний такие высказывания.

1) 45 кратное 3 и 42 кратное 3.

2) 45 кратное 3 и 12 не кратное 3;

3) и ;

4) ;

5) Если число 212 делится на 3 и 4, то оно делится и на 12;

6) Число 212 – трехзначное число, которое делится на 3 и 4.

Выполнение.

1) Атомы: : «45 кратное 3»; : «42 кратное 3». Формула логики высказываний: . Так как и , то (заданное высказывание истинно).

2) Атомы: : «45 кратное 3»; : «12 кратное 3». Формула логики высказывания: . Так как и , то (заданное высказывание ложно).

3) Атомы: : «»; : «». Формула логики высказывания . Так как и , то .

4) Атом : «». Формула логики высказываний (атомарная формула). Так как , то заданное высказывание истинно.

5) Атомы: : «число 212 делится на 3»; : «число 212 делится на 4», : «число 212 делится на 12». Формула логики высказываний: . Так как , , , то .

6) Атомы: : «число 212 делится на 3»; : «число 212 делится на 4», : «212 – трехзначное число». Формула логики высказывание . Так как , , , то .

УПРАЖНЕНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

Какие из утверждений – высказывания?

1) Нью-Йорк – столица Канады;

2) Лондон – город на правом берегу Дона;

3) Студент физико-математического факультета;

5) 5 – логическое значение;

.