Что такое истинное высказывание

01.10.2019

Пример 1. Установить истинность высказывания · С
Решение. В состав сложного высказывания входят 3 простых высказывания: А, В, С. В таблице заполняются колонки значениями (0, 1). Указываются все возможные ситуации. Простые высказывания от сложных отделяются двойной вертикальной чертой.
При составлении таблицы надо следить за тем, чтобы не перепутать порядок действий; заполняя столбцы, следует двигаться “изнутри наружу”, т.е. от элементарных формул к более и более сложным; столбец, заполняемый последним, содержит значения исходной формулы.

А	В	С		А+		· С



0	1	1	0	0	1	1

Из таблицы видно, что данное высказывание истинно только в случае, когда А=0, В=1, С=1. Во всех остальных случаях оно ложно.

Эквивалентность высказываний.

С помощью таблиц истинности можно установить эквивалентность двух или нескольких высказываний.

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

Пример 2. Утверждается, что высказывание А+В· С эквивалентно высказыванию (А+В)· (А+С)
Решение. Проверка ведется путем составления таблицы истинности.


А	В	С	В С	А+В· С	А+В	А+С	(А+В)· (А+С)

Сравнивая 5-ю и 8-ю колонки убеждаемся, что все значения, получаемые по формуле А+В· С, совпадают со значениями, получаемыми по формуле (А+В)· (А+С), т.е. высказывания эквивалентны (равносильны). Одно может заменить другое.
Эквивалентные (равносильные) высказывания соединяют знаком º А + В·Сº (А+В)· (А+С).
Отметим различие между эквивалентностью и эквиваленцией.
Эквиваленция является логической операцией, позволяющей по двум заданным высказываниям А и В построить новое А« В.
Эквивалентность же является отношением между двумя составными высказываниями, состоящим в том, что их значения истинности всегда одни и те же.

Тавтология.

Пусть дано высказывание А· и необходимо составить таблицу истинности.
Высказывание А· ложно, истинность его не зависит от истинности высказывания А.

Рассмотрим высказывание В+ .
В этом случае высказывание В+ всегда истинно, независимо от истинности В.

В		В+

Высказывания, истинность которых постоянна и не зависит от истинности входящих в них простых высказываний, а определяется только их структурой, называются тождественными или тавтологиями.
Различают тождественно-истинные и тождественно-ложные высказывания.
В формулах каждое тождественно-истинное высказывание заменяется 1, а тождественно-ложное - 0. Закон исключенного третьего.
A· º 0
В+ º 1

Пример 3. Докажите тавтологию (XÙ Y)® (XÚ Y)
Решение.

Т.к. высказывание (XÙ Y)® (XÚ Y) всегда истинно, то оно является тавтологией.

Пример 4. Докажите тавтологию ((X® Y)Ù (Y® Z))® (X® Z)
Решение.
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ F1 _ _ _ _ F2 _ _ _ _ _ F

X	Y	Z	X® Y	Y® Z	X® Z	F1Ù F2	(F1Ù F2) ® F3

Из таблицы видно, что исследуемое высказывание - тавтология, т.к. оно истинно постоянно.

Вопросы и задания.

1. Какому из ниже приведенных высказываний:

а) (A+C); б) +B; в) +C); г) A+ ;
эквивалентно высказывание (B+C)

2. Установите с помощью таблиц истинности, какие из следующих формул - тавтологии:
а) « ); б) ; в) ;

г) ; д) (X® Y)« (Y® X); е) (X® Y)« ;

ж) (X® Y)« .

3. Установить истинность высказывания

4. Эквивалентны ли высказывания:
и ?

5. Установить, является ли данное высказывание тавтологией:
а) ; б)

6. Для каждой формулы придумайте формализуемые ими предложения:
а) ; б) ; в) .

7. Из простых высказываний: “Виктор хороший пловец” - А; “Виктор хорошо ныряет” - В; “Виктор хорошо поет” - С, составлено сложное высказывание, формула которого имеет вид:
X=(A+C)· (A+B). Установить, эквивалентно ли высказывание Х высказыванию: “Виктор - хороший пловец и Виктор хорошо поет”.

8.
а) ; б) ;
в) ((X1® X2)® X3)Ù (X3« X1); г) ((X® Y)Ù (Y® Z))® (X® Z).

9. Установить истинность высказываний:
а) , , ;
б) , , ;
в) , , ;
г) , , .

Законы логики

Равносильности формул логики высказываний часто называют законами логики.
Знание законов логики позволяет проверять правильность рассуждений и доказательств.
Нарушения этих законов приводят к логическим ошибкам и вытекающим из них противоречиям.
Перечислим наиболее важные из них:
1. Xº X Закон тождества
2. Закон противоречия
3. Закон исключенного третьего
4. Закон двойного отрицания
5. XÙ Xº X , XÚ Xº C Законы идемпотентности
6. C Ù U º U Ù C , C Ú U º U Ú C Законы коммутативности (переместительности)
7 . (C Ù U) Ù Z ºC Ù (U Ù Z) , (C Ú U) Ú Z º C Ú (U Ú Z) - Законы ассоциативности (сочетательности)
8. C Ù (U Ú Z) º (C Ù U) Ú (C Ù Z) , C Ú (U Ù Z) º (C Ú U) Ù (C Ú Z) - Законы дистрибутивности (распределительности)
9. , Законы де Моргана
10. XÙ 1º C , C Ú 0 º C
11. C Ù 0 º 0 , C Ú 1 º 1
12. C Ù (C Ú U) º C , C Ú (C Ù U) º C Законы поглощения
13. (C Ú U) Ù ( Ú U) º U , (C Ù U) Ú ( Ú U) º U Законы склеивания

1-й закон сформулирован древнегреческим философом Аристотелем. Закон тождества утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует.

Закон противоречия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием.
“Это яблоко спелое” и “Это яблоко не спелое”.

Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно либо ложно. Третьего не дано. “Сегодня я получу 5 либо не получу”. Истинно либо суждение, либо его отрицание.

Закон двойного отрицания. Отрицать отрицание какого-нибудь высказывания - то же, что утверждать это высказывание.
“ Неверно, что 2× 2¹ 4”

Законы идемпотентности. В алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых “сомножителей” равносильна одному из них.

Законы коммутативности и ассоциативности. Конъюнкция и дизъюнкция аналогичны одноименным знакам умножения и сложения чисел.
В отличие от сложения и умножения чисел логическое сложение и умножение равноправны по отношению к дистрибутивности: не только конъюнкция дистрибутивна относительно дизъюнкции, но и дизъюнкция дистрибутивна относительно конъюнкции.

Смысл законов де Моргана (Август де Морган (1806-1871) - шотландский математик и логик) можно выразить в кратких словесных формулировках:
- отрицание логического произведения эквивалентно логической сумме отрицаний множителей.
- отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых.

Доказать законы логики можно:
1) с помощью таблиц истинности;
2) с помощью равносильностей.
Докажем законы склеивания и поглощения с помощью равносильностей:
1) (C Ú U) Ù ( Ú U) º (C + U) × ( + U) º C × + U × + U × U + C × U ºU × + U + C × U º U × +U (1 + C) º U × + U º U ( + 1) º U (Закон склеивания)

2) C Ù (C Ú U) º C × C +C × U º C +C × U º C (1 + U) º C (Закон поглощения)

Задание. Доказать законы логики с помощью таблиц истинности.

Тождественные преобразования

Упрощение формул.

Пример 1. Упростить формулу (АÚВ)· (АÚС)
Решение.
а) Раскроем скобки (A Ú B) · (A ÚC) º A · A Ú A · C Ú B · A Ú B · C
б) По закону равносильности A · A º A , следовательно,
A · A Ú A · C ÚB · A Ú B · C º A ÚA · C Ú B · A Ú B · C
в) В высказываниях А и А· C вынесем за скобки А и используя свойство АÚ1º 1, получим АÚА· СÚ B · A Ú B · C º A ·(1 ÚС) Ú B · A Ú B · Сº A ÚB · A Ú B· С
г) Аналогично пункту в) вынесем за скобки высказывание А.
AÚB · A Ú B · Сº A (1ÚB)ÚB · Сº A Ú B · С
Таким образом, мы доказали закон дистрибутивности.

2. Преобразования “поглощение” и “склеивание”

Пример 2. Упростить выражение АÚ A · B

Решение. A ÚA · B º A (1 Ú B) º A - поглощение

Пример 3. Упростить выражение A · B Ú A · - знаки логического сложения;
- знаки логического умножения.
А будут использованы:
- знаки отрицания и логического умножения;
- знаки отрицания и логического сложения.

Пример 5. Преобразовать формулу так, чтобы в ней не использовались знаки логического сложения.
Решение. Воспользуемся законом двойного отрицания, а затем формулой де Моргана.

Пример 6. Преобразовать формулу так, чтобы в ней не использовались знаки логического умножения.
Решение. Используя формулы де Моргана и закон двойного отрицания получим:

1.1 . Какие из следующих предложений являются высказываниями?

а) Москва  столица России.

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

в) Треугольник ABC подобен треугольнику А"В"С".

г) Луна есть спутник Марса.

е) Кислород  газ.

ж) Каша  вкусное блюдо.

з) Математика  интересный предмет.

и) Картины Пикассо слишком абстрактны.

к) Железо тяжелее свинца.

л) Да здравствуют музы!

м) Треугольник называется равносторонним, если его стороны равны.

н) Если в треугольнике все углы равны, то он равносторонние.

о) Сегодня плохая погода.

п) В романе А. С. Пушкина «Евгений Онегин» 136 245 букв.

р) Река Ангара впадает в озеро Байкал.

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

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

ж) Предложение не является высказыванием, так как понятие «вкусное блюдо» слишком неопределенно.

п) Предложение  высказывание, но для выяснения его значения истинности нужно затратить немало времени.

1.2. Укажите, какие из высказываний предыдущей задачи истинные, а какие  ложные.

1.3. Сформулируйте отрицания следующих высказываний; укажите значения истинности данных высказываний и их отрицаний:

а) Волга впадает в Каспийское море.

б) Число 28 не делится на число 7.

д) Все простые числа нечетны.

1.4. Установите, какие из высказываний в следующих парах являются отрицаниями друг друга и какие  нет (объясните почему):

а) 2 < 0, 2 > 0. -

б) 6 < 9, 6  9.

в) «Треугольник ABC прямоугольный», «Треугольник ABC тупоугольный».

г) «Натуральное число n четно», «Натуральное число n нечетно».

д) «Функция f нечетна», «Функция f четна».

е) «Все простые числа нечетны», «Все простые числа четны».

ж) «Все простые числа нечетны», «Существует простое четное число».

з) «Человеку известны все виды животных, обитающих на Земле», «На Земле существует вид животных, не известный человеку».

и) «Существуют иррациональные числа», «Все числа рациональные».

Решение. а) Высказывание «2 > 0» не является отрицанием "высказывания «2 < 0», потому что требование не быть меньше 0 оставляет две возможности: быть равным 0 и быть больше 0. Таким образом, отрицанием высказывания «2 < 0» является высказывание «2  0».

1.5. Следующие высказывания запишите без знака отрицания:

а)
; в)
;

б)
; г)
.

1.6.

а) Ленинград расположен на Неве и 2 + 3 = 5.

б) 7  простое число и 9  простое число.

в) 7  простое число или 9  простое число.

г) Число 2 четное или это число простое.

д) 2  3, 2  3, 2 2  4, 2 2  4.

е) 2 2 = 4 или белые медведи живут в Африке.

ж) 2 2 = 4, и 2 2  5, и 2 2  4.

Решение. а) Так как оба простых высказывания, к которым применяется операция конъюнкции, истинны, поэтому на основании определения этой операции и их конъюнкция есть истинное высказывание.

1.7. Определите значения истинности высказываний А, В, С, D и Е, если:

 истинные высказывания, а

 ложные.

Решение. в) Дизъюнкция высказываний есть истинное высказывание лишь в случае, когда по меньшей мере одно из входящих в дизъюнкцию составляющих высказываний (членов дизъюнкции) истинно. В нашем случае второе составляющее высказывание «2 2 = 5» ложно, а дизъюнкция двух высказываний истинна. Поэтому первое составляющее высказывание С истинно.

1.8. Сформулируйте и запишите в виде конъюнкции или дизъюнкции условие истинности каждого предложения (а и b - действительные числа):

а)
г)ж)

б)
д)
з)

в)
е)
и)

Решение. г) Дробь равна нулю лишь в случае, когда числитель равен нулю и знаменатель не равен нулю, т. е. (а = 0) & (b  0).

1.9. Определите значения истинности следующих высказываний:

а) Если 12 делится на 6, то 12 делится на 3.

б) Если 11 делится на 6, то 11 делится на 3.

в) Если 15 делится на 6, то 15 делится на 3.

г) Если 15 делится на 3, то 15 Делится на 6.

д) Если Саратов расположен на Неве, то белые медведи обитают в Африке.

е) 12 делится на 6 тогда и только тогда, когда 12 делится на 3.

ж) 11 делится на 6 тогда и только тогда, когда 11 делится на 3.

з) 15 делится на 6 тогда и только тогда, когда 15 делится на 3.

и) 15 делится на 5 тогда и только тогда, когда 15 делится на 4.

к) Тело массой m обладает потенциальной энергией mgh тогда и только тогда, когда оно находится на высоте h над поверхностью земли.

Решение. а) Так как высказывание-посылка «12 делится на 6» истинно и, высказывание-следствие «12 делится на 3» истинно, то и составное высказывание на основании определения импликации также истинно.

ж) Из определения эквивалентности видим, что высказывание вида
истинно, если логические значения высказыванийР и Q совпадают, и ложно в противном случае. В данном примере оба высказывания к которым применяется связка «тогда и только тогда», ложны. Поэтому все составное высказывание истинно.

1.10. Пусть через А обозначено высказывание «9 делится на 3», а через В  высказывание «8 делится на 3». Определите значения истинности следующих высказываний:

а)
г)
ж)
к)

б)
д)
з)
л)

в)
е)
и)
м)

Решение. е) Имеем
,
. Поэтому

1.11.

а) Если 4  четное число, то А.

б) Если В, то 4  нечетное число.

в) Если 4  четное число, то С.

г) Если D, то 4  нечетное число.

Решение. а) Импликация двух высказываний есть ложное высказывание лишь в единственном случае, когда посылка истинна, а заключение ложно. В данном случае посылка «4  четное число» истинна и по условию все высказывание также истинно. Поэтому заключение А ложным быть не может, т. е. высказывание А истинно.

1.12. Определите значения истинности высказываний А, В, С и D в следующих предложениях, из которых первые два истинны, а последние два ложны:

а)
; б)
;

в)
; г)
.

1.13. Пусть через А обозначено высказывание «Этот треугольник равнобедренный», а через В  высказывание «Этот треугольник равносторонний». Прочитайте следующие высказывания:

а)
г)

б)
д)

в)
е)

Решение. е) Если треугольник равнобедренный и неравносторонний, то неверно, что он неравнобедренный.

1.14. Следующие составные высказывания расчлените на простые и запишите символически, введя буквенные обозначения для простых их составляющих:

а) Если 18 делится на 2 и не делится на 3, то оно не делится на 6.

б) Произведение трех чисел равно нулю тогда и только тогда, когда одно из них равно нулю.

в) Если производная функция в точке равна нулю и вторая производная этой функции в той же точке отрицательна, то данная точка есть точка максимума этой функции.

г) Если в треугольнике медиана не является высотой и биссектрисой, то этот треугольник не равнобедренный и не равносторонний.

Решение. г) Выделим и следующим образом обозначим простейшие составляющие высказывания:

А: «В треугольнике медиана является высотой»;

В: «В треугольнике медиана является биссектрисой»;

С: «Этот треугольник равнобедренный»;

D: «Этот треугольник равносторонний».

Тогда данное высказывание символически записывается так:

1.15. Из двух данных высказываний А и В постройте составное высказывание с помощью операций отрицания, конъюнкции и дизъюнкции, которое было бы:

а) истинно тогда и только тогда, когда оба данных высказывания ложны;

б) ложно тогда и только тогда, когда оба данных высказывания истинны.

1.16. Из трех данных высказываний А, В, С постройте составное высказывание, которое истинно, когда истинно какое-либо одно из данных высказываний, и только в этом случае.

1.17. Пусть высказывание
истинно. Что можно сказать о логическом значении высказывания?

1.18. Если высказывание
истинно (ложно), то что можно сказать о логическом значении высказываний:

а)
; б)
; в)
; г)
?

1.19. Если высказывание
истинно, а высказывание
ложно, то что можно сказать о логическом значении высказывания
?

1.20. Существуют ли три таких высказывания А, В, С, чтобы одновременно высказывание
было истинным, высказывание
 ложным и высказывание
 ложным?

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

Решение. а) Поскольку заключение импликации истинно, то и вся импликация будет истинным высказыванием независимо от логического значения посылки.

Урок №2

Алгебра высказываний. Логические операции.

(урок комбинированный, включающий повторение предыдущей темы,

введение нового материала и закрепление)

Цель урока: Сформировать у учащихся понятия: логическое высказывание, логические операции.

Задачи урока :

Повторить основные материалы 1 урока (формы человеческого мышления: понятие, суждение, умозаключение);

Познакомить с определением алгебры высказываний;

Познакомить с основными логическими операциями.

Требования к знаниям и умениям:

Учащиеся должны знать:

Что изучает алгебра высказываний и что является объектом изучения алгебры высказываний;

Значения понятий: логическое высказывание, логические операции;

Таблицы истинности логических операций.

Учащиеся должны уметь:

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

Определять значения логических высказываний;

Называть логические операции и строить для них таблицы истинности.

Этапы урока

I. Организационный момент. Постановка цели урока. 2 мин.

II. Повторение. 7мин.

III. Проверка домашнего задания. 5 мин.

IV. Введение нового материала. 20 мин.

V. Закрепление. 7 мин.

VI. Подведение итогов урока. 3 мин.

VII. Постановка домашнего задания. 1 мин.

Ход урока

II. Повторение .

1) Повторение основных определений и понятий 1 урока:

· Понятие – форма мышления, в которой отражены существенные признаки объектов.

o Объём понятия – множество предметов, каждому из которых принадлежат признаки, составляющие содержание понятия.

Привести примеры .

· Суждение (высказывание, утверждение) - форма мышления, в которой что-либо утверждается или отрицается о предметах, их свойствах или отношениях между ними.

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

· Умозаключение - форма мышления, посредством которой из одного или нескольких суждений, называемых посылками, по определенным правилам вывода получаем суждение-заключение (вывод умозаключения)

- Определите, какие из перечисленных фраз являются высказываниями и почему?

1. Как хорошо быть генералом!

3. Познай самого себя.

4. Все медведи живут на севере.

5. Революция не может быть мирной и бескровной.

(Примеры 1 и 3 не являются высказываниями, т. к. являются восклицательным и побудительным предложениями соответственно).

- Теперь определите, простые или составные суждения даны .

(В 5 примере можно разбить на два простых утверждения, значит, оно составное.)

- Определите значения высказываний (истина или ложь).

На 6 примере убеждаемся, что содержание высказывания часто субъективная характеристика. Обоснование истинности или ложности простых высказываний решается вне науки логики. Например, опираясь на свой жизненный опыт, мы присваиваем определённое значение суждению 6.

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

В примере 7 значение высказывания решается в курсе геометрии, а в 5 утверждении в курсе истории.

Результаты оформляются в виде следующей таблицы:

Фразы	Высказывания	Истина или ложь	Простые высказывания
1. Как хорошо быть генералом!
2. Без труда не выловишь и рыбку из пруда.
3. Познай самого себя.
4. Все медведи живут на севере.
5. Революция не может быть мирной и бескровной.
6. Талант всегда пробьёт себе дорогу.
7. Сумма углов треугольника равна 1800.

На прошлом уроке мы говорили, что каждое высказывание состоит из трех элементов:
субъекта, предиката и связки . Субъект (S) - понятие о предмете. Предикат (P) - понятие о свойствах и отношениях предмета. Связка - отношение между субъектом и предикатом.

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

Без труда не выловишь и рыбку из пруда.

Все медведи живут на севере.

Талант всегда пробьёт себе дорогу.

Сумма углов треугольника равна 1800.

III. Проверка домашнего задания:

Карточка для домашней работы

1.Из приведенных простых высказываний составьте и запишите не менее 3-ёх составных высказываний:

1) Поедем на дачу.

2) Хорошая погода.

3) Плохая погода.

4) Мы поедем на пляж.

5) Антон приглашает нас в театр .

2. Выведите, если это возможно, заключение из каждой пары посылок:

А) Все птицы – животные.

Все воробьи – птицы.

Б) Некоторые уроки трудны.

Всё, что трудно, требует внимания.

В) Ни один добрый поступок не является незаконным.

Всё, что законно, можно делать без страха.

А) Тем, кто лыс, расчёска не нужна.

Ни одна ящерица не имеет волос.

Следовательно, ящерицам расчёска не нужна.

Б) Всем, кто отлично закончит 3 четверть, подарят компьютер.

Ты закончил 3 четверть без троек.

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

VI. Объяснение нового материала

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

Идею о возможности математизации логики высказал еще в XVII веке. Он пытался создать универсальный язык, с помощью которого каждому понятию и высказыванию можно было бы дать числовую характеристику и установить такие правила оперирования с этими числами, которые позволили бы сразу определить, истинно данное высказывание или ложно. То есть споры между людьми можно было бы разрешать посредством вычислений. Идея Лейбница оказалось ложной, так как невозможно (не найдены способы) свести человеческое мышление к некоторому математическому исчислению.

Однако, подлинный прогресс этой науки был достигнут в середине XIX века прежде всего благодаря трудам Дж. Буля "Математический анализ логики". Он перенес на логику законы и правила алгебраических действий, ввёл логические операции, предложил способ записи высказываний в символической форме.

В развитии математической логики приняли участие многие выдающиеся математики и логики конца XIX и XX веков, в том числе К. Гедель (австр.), Д. Гильберт (нем.), С. Клини (амер.), Э. Пост (амер.), А. Тьюринг (анг.), А. Чёрч (амер.), и многие другие.

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

Таким образом, объектами изучения алгебры логики являются высказывания.

Под высказыванием (суждением) будем понимать повествовательное предложение, относительно которого можно однозначно сказать, истинно оно или ложно.

Обозначать высказывания будем большими латинскими буквами. Если высказывание А истинное, то будем писать "А = 1" и говорить: "А - истинно". Если высказывание Х ложно, то будем писать "Х = 0" и говорить "Х ложно".

Обоснование истинности или ложности простых высказываний решается вне алгебры логики. Например, истинность или ложность высказывания «Сумма углов треугольника равно 180о» устанавливается геометрией, причём в геометрии Евклида это высказывание является истинным, а в геометрии Лобачевского – ложным.

Алгебра логики отвлекается от смыслового содержания высказываний. Её интересует только один факт – истинно или ложно данное высказывание. Такое суждение интересов даёт возможность изучать высказывания алгебраическими методами.

Логические операции

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

Дизъюнкция (логическое сложение)

Импликация (логическое следование)

Эквивалентность (логическое равенство)

1) Инверсия (логическое отрицание)

Инверсия (логическое отрицание) – это логическая операция, которая каждому данному высказыванию ставит в соответствие новое высказывание, которое истинно, если данное высказывание – ложно, и ложно, если данное высказывание истинно.

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

Обозначение инверсии: ; неА ; А; NOT А

0 " style="border-collapse:collapse;border:none">

Образуется из простого высказывания с помощью добавления частицы НЕ к сказуемому или использованием оборота речи "НЕВЕРНО, ЧТО...".

Пример: А = "На улице дождь"

= "Неверно, что на улице дождь"

Задание 1. Приведите пример высказывания и его отрицания.

Определите истинность каждого.

Итак, инверсия высказывания истинна, когда высказывание ложно.

2) Конъюнкция (логическое умножение)

истинно тогда и только тогда, когда оба исходных высказывания истинны.

Обозначение конъюнкции: А &В , А andВ , А LВ , А В .

Таблица истинности:

		А &В

Образуется соединением двух высказываний в одно с помощью союза «И»

Пример: А = "На улице дождь"

В= "Небо голубое"

А &В = "На улице дождь и небо голубое"

Задание 2. а) Приведите примеры двух высказываний и получите составное высказывание используя логическую связку "И".

Итак, конъюнкция двух высказываний истинна тогда и только тогда, когда оба исходных высказывания истинны.

3) Дизъюнкция (логическое сложение) – это логическая операция, ставящая в соответствие каждым двум высказываниям новое высказывание, которое

истинно тогда и только тогда, когда хотя бы одно из двух исходных высказываний истинно.

Обозначение дизъюнкции: А V В , А OR В , А +В .

0 " style="border-collapse:collapse;border:none">

А V В

Образуется соединением двух высказываний в одно с помощью союза «ИЛИ»

Пример: А = "На улице дождь"

В= "Небо голубое"

А V В = "На улице дождь или небо голубое"

Задание 3. а) Приведите примеры двух высказываний и получите составное высказывание используя связку "ИЛИ".

Итак, дизъюнкция двух высказываний истинна тогда и только тогда, когда хотя бы одно из двух исходных высказываний истинно.

4) Импликация (логическое следование) – это логическая операция, ставящая в соответствие каждым двум высказываниям новое высказывание, которое

ложно тогда и только тогда, когда первое высказывание (условие) истинно, а второе высказывание (следствие) ложно.

Обозначение дизъюнкции: А ® В .

Таблица истинности: Диаграмма Эйлера:

«ЕСЛИ …, ТО …»

Если клятва дана, то она должна выполняться.

Если число делится на 9, то оно делится и на 3.

Пример: А = " На улице дождь"

В= "Небо голубое"

А ® В = "Если на улице дождь, то небо голубое"

Задание 4 . а) Приведите примеры двух высказываний и получите составное высказывание, используя связку "ЕСЛИ, ТО...".

б) Определите истинность или ложность каждого из трех высказываний

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

5) Эквивалентность (логическое равенство) – это логическая операция, ставящая в соответствие каждым двум высказываниям новое высказывание, которое

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

Обозначение дизъюнкции: А « В, А = В, А≡В .

Таблица истинности: Диаграмма Эйлера:

Образуется соединением двух высказываний в одно с помощью оборота речи «…ТОГДА И ТОЛЬКО ТОГДА, КОГДА…»

Угол называется прямым тогда и только тогда, когда он равен 900

Все законы математики, физики, все определения – эквивалентность высказываний

Две прямые параллельны тогда и только тогда, когда они не пересекаются.

Пример: А = "На улице дождь"

В= "Небо голубое"

А « В = "На улице дождь тогда и только тогда, когда небо голубое"

Задание 5. а) Приведите примеры двух высказываний и получите составное высказывание используя связку речи «…ТОГДА И ТОЛЬКО ТОГДА, КОГДА…»

б) Определите истинность или ложность каждого из трех высказываний.

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

VI. Закрепление изученного.

1. Объясните, почему следующие предложения не являются высказываниями :

· Какого цвета этот дом?

· Число Х не превосходит единицы.

· Посмотрите в окно.

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

· Эта тема скучна.

· Вы были в театре?

2. Объясните, почему формулировка любой теоремы является высказыванием.

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

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

Коля спросил: «Как пройти к Большому театру?» Как пройти в библиотеку? Картины Пикассо слишком абстрактны. Решение задачи – информационный процесс. Число 2 является делителем числа 7 в некоторой системе счисления.

5. Выбрать истинные высказывания:

· “Число 28 является совершенным числом”

· “Без труда не выловишь и рыбку из пруда”

· “Талант всегда пробьёт себе дорогу”

· “Некоторые животные мыслят”

· “Информатика - наука об алгоритмах”

· “2+3*5=30”

· “Все ученики любят информатику”

7. Какая логическая операция соответствует данной таблице истинности?

8. Какая логическая операция соответствует данной таблице истинности?

9. Какая логическая операция соответствует данной таблице истинности?

10. Какая логическая операция соответствует данной таблице истинности?

Итог урока:

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

2. Выучить все определения в тетради из конспекта урока .

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

План

Высказывания с внешним отрицанием.

Конъюнктивные высказывания.

Дизъюнктивные высказывания.

Строго-дизъюнктивные высказывания.

Высказывания об эквивалентности.

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

Высказывания с внешним отрицанием.

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

В высказываниях с внешним отрицанием отрицается ситуация в А. Например, если А: “Волга впадает в Черное море”, то ùА: “Неверно, что Волга впадает в Черное море”.

Конъюнктивные высказывания.

Конъюнктивными высказываниями являются такие, в которых утверждается одновременное наличие двух ситуаций. Конъюнктивные высказывания образуются из двух высказываний при помощи союзов “и”, “а”, “но”. Форма конъюнктивного высказывания: (А&В). Каждое из высказываний А и В может принимать как значение “истина”, так и значение “ложь”. Эти значения для краткости обозначаются буквами и, л . Таблица истинности для конъюнктивных высказываний имеет следующий вид:

В конъюнктивных высказываниях утверждается, что ситуация, описанная в А и в В имеют место одновременно. Примеры конъюнктивных высказываний: “Земля - планета, а Луна - спутник”; “Петров хорошо освоил логику, но Сидоров освоил логику плохо”; “На улице темно, и в аудитории горит свет”; “Петров всучил чиновнику взятку деньгами, а Сидоров - бутылкой”.

Дизъюнктивные высказывания.

Дизъюнктивные высказывания - это высказывания, в которых утверждается наличие по крайней мере одной из двух ситуаций, описанных в А и В. Дизъюнкция обозначается символом V и выражается в естественном языке союзом “или”.

Табличное определение знака дизъюнкции имеет следующий вид:

Пример дизъюнктивного высказывания: “Роман Сергеевич Иванов является преподавателем, или Роман Сергеевич Иванов является аспирантом”.

Строго-дизъюнктивные высказывания .

Строго-дизъюнктивными называются высказывания, в которых утверждается наличие ровно одной из двух ситуаций, описанных в А и В. Такие высказывания чаще всего осуществляются посредством предложений с союзом “или..., или...” (“либо..., либо...”). Строгая дизъюнкция обозначается символом V* (читается “либо..., либо...”).

Табличное определение знака строгой дизъюнкции имеет следующий вид:

Пример строго-дизъюнктивного высказывания: “Либо на улице солнечно, либо идет дождь”.

Свойства

Рассмотрим несколько свойств декартова произведения:

1. Если A ,B - конечные множества, то A ×B - конечное. И наоборот, если одно из множеств-сомножителей бесконечное, то и результат их произведения - бесконечное множество.

2. Количество элементов в декартовом произведении равно произведению чисел элементов множеств-сомножителей (в случае их конечности, разумеется): |A ×B |=|A |⋅|B | .

3. A np ≠(A n ) p - в первом случае целесообразно рассмотреть результат декартова произведения как матрицу размеров 1×np , во втором же - как матрицу размеров n ×p .

4. Коммутативный закон не выполняется, т.к. пары элементов результата декартова произведения упорядочены: A ×B ≠B ×A .

5. Ассоциативный закон не выполняется: (A ×B )×C ≠A ×(B ×C ) .

6. Имеет место дистрибутивность относительно основных операциях на множествах: (A ∗B )×C =(A ×C )∗(B ×C ),∗∈{∩,∪,∖}

11. Понятие высказывания. Элементарные и составные высказывания.

Высказывание - это утверждение или повествовательное предложение, о котором можно сказать, что оно истинно (И-1) или ложно (Л-0), но не то и другое одновременно.

Например, «Сегодня идет дождь», «Иванов выполнил лабораторную работу №2 по физике».

Если у нас имеется несколько исходных высказываний, то из них при помощи логических союзов или частиц мы можем образовывать новые высказывания, истинностное значение которых зависит только от истинностных значений исходных высказываний и от конкретных союзов и частиц, которые участвуют в построении нового высказывания. Слова и выражения «и», «или», «не», «если... , то», «поэтому», «тогда и только тогда» являются примерами таких союзов. Исходные высказывания называются простыми , а построенные из них с помощью тех или иных логических союзов новые высказывания - составными . Разумеется, слово «простые» никак не связано с сутью или структурой исходных высказываний, которые сами могут быть весьма сложными. В данном контексте слово «простой» является синонимом слова «исход-ный». Важно то, что значения истинности простых высказываний предполагаются известными или заданными; в любом случае они никак не обсуждаются.

Хотя высказывание типа «Сегодня не четверг» не составлено из двух различных простых высказываний, для единообразия конструкции оно также рассматривается как составное, по-скольку его истинностное значение определяется истинностным значением другого высказыва-ния «Сегодня четверг»

Пример 2. Cледующие высказывания рассматриваются как составные:

Я читаю «Московский комсомолец» и я читаю «Коммерсант».

Если он сказал это, значит, это верно.

Солнце не является звездой.

Если будет солнечно и температура превысит 25 0 , я приеду поездом или автомобилем

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

12. Операции над высказываниями.

1. Операция отрицания.

Отрицанием высказывания А (читается «не А », «неверно, что А »), которое истинно, когда А ложно и ложно, когда А – истинно.

Отрицающие друг друга высказывания А и называются противоположными.

2. Операция конъюнкции .

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

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

Пусть дано высказывание А – «в марте температура воздуха от 0 С до +7 С » и высказывание В – «в Витебске идет дождь». Тогда А В будет следующей: «в марте температура воздуха от 0 С до +7 С и в Витебске идет дождь». Данная конъюнкция будет истинной, если будут высказывания А и В истинными. Если же окажется, что температура была меньше 0 С или в Витебске не было дождя, то А В будет ложной.

3 . Операция дизъюнкции .

Дизъюнкцией высказываний А и В называется высказывание А В (А или В ), которое истинно тогда и только тогда, когда хотя бы одно из высказываний истинно и ложно – когда оба высказывания ложны.

Дизъюнкцию высказываний называют также логической суммой А+В.

Высказывание «4<5 или 4=5 » является истинным. Так как высказывание «4<5 » – истинное, а высказывание «4=5 » – ложное, то А В представляет собой истинное высказывание «4 5 ».

4 . Операция импликации .

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

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

13. Таблицы истинности высказываний.

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

Таблицы истинности применяются для:

Вычисления истинности сложных высказываний;

Установления эквивалентности высказываний;

Определения тавтологий.

Установление истинности сложных высказываний.

Пример 1. Установить истинность высказывания · С

Решение. В состав сложного высказывания входят 3 простых высказывания: А, В, С. В таблице заполняются колонки значениями (0, 1). Указываются все возможные ситуации. Простые высказывания от сложных отделяются двойной вертикальной чертой.
При составлении таблицы надо следить за тем, чтобы не перепутать порядок действий; заполняя столбцы, следует двигаться “изнутри наружу”, т.е. от элементарных формул к более и более сложным; столбец, заполняемый последним, содержит значения исходной формулы.

А	В	С	А+	· С

14. Равносильные формулы.

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

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

Для любых формул А , В , С справедливы равносильности.

I. Основные равносильности

закон идемпотентности

1-истина

0-ложь

Закон противоречия

Закон исключенного третьего

закон поглощения

формулы расщепления

закон склеивания

II. Равносильности, выражающие одни логические операции через другие.

закон де Моргана

III. Равносильности, выражающие основные законы алгебры логики.

коммутативный закон

ассоциативный закон

дистрибутивный закон

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

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

1. Законы (тождественно-истинные формулы) – формулы, которые при любых интерпретациях пропозициональных переменных принимают значение «истинно» ;

2. Противоречия (тождественно-ложные формулы) – формулы, которые при любых интерпретациях пропозициональных переменных принимают значение «ложно» ;

3. Выполнимые формулы – такие, которые принимают значение «истинно» хотя бы при одном наборе значений истинности входящих в их состав пропозициональных переменных.

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

1. Закон тождества: ;

2. Закон противоречия: ;

3. Закон исключенного третьего: ;

4. Законы коммутативности и : , ;

5. Законы дистрибутивности относительно ,и наоборот: , ;

6. Закон удаления истинного члена конъюнкции: ;

7. Закон удаления ложного члена дизъюнкции: ;

8. Закон контрапозиции: ;

9. Законы взаимовыразимости пропозициональных связок: , , , , , .

Процедура разрешимости – метод, позволяющий для каждой формулы установить является она законом, противоречием или выполнимой формулой. Самой распространенной процедурой разрешимости является метод истинностных таблиц. Однако он не единственный. Эффективным методом разрешимости является метод нормальных форм для формул логики высказываний. Нормальной формой формулы логики высказываний является форма, не содержащая знака импликации « ». Различают конъюнктивную и дизъюнктивную нормальные формы. Конъюнктивная форма содержит только знаки конъюнкции « ». Если в формуле, приведенной к конъюнктивной нормальной форме, встречается подформула вида , то вся формула в этом случае является противоречием . Дизъюнктивная форма содержит только знаки дизъюнкции « ». Если в формуле, приведенной к дизъюнктивной нормальной форме, встречается подформула вида , то вся формула в этом случае является законом . Во всех остальных случаях формула является выполнимой формулой .

16. Предикаты и операции над ними. Кванторы.

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

В зависимости от числа переменных, входящих в предложение, различают одноместные, двухместные, трехместные и т.д. предикаты, обозначаемые соответственно: А(х ), В(х , у ), С(х , у , z ).

Если задан некоторый предикат, то с ним связаны два множества:

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

2. Множество истинности Т, состоящее из всех тех значений переменных, при подстановке которых в предикат получается истинное высказывание.

Множество истинности предиката всегда является подмножеством его области определения, то есть .

Над предикатами можно совершать те же операции, что и над высказываниями.

1. Отрицанием предиката А(х ), заданного на множестве Х, называется предикат , истинный при тех значениях , при которых предикат А(х ) обращается в ложное высказывание, и наоборот.

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

Множество истинности предиката является дополнением к множеству истинности предиката А(х ). Обозначим через Т А множество истинности предиката А(х ), а через Т - множество истинности предиката . Тогда .

2. Конъюнкцией предикатов А(х ) и В(х х ) В(х х Х, при которых оба предиката обращаются в истинные высказывания.

Множество истинности конъюнкции предикатов есть пересечение множеств истинности предиката А(х ) В(х ). Если обозначить множество истинности предиката А(х) через Т А, а множество истинности предиката В(х) через Т В и множество истинности предиката А(х) В(х) через , то

3. Дизъюнкцией предикатов А(х) и В(х ), заданных на множестве Х, называется предикат А(х ) В(х ), обращающийся в истинное высказывание при тех и только тех значениях х Х, при которых хотя бы один из предикатов обратился в истинное высказывание.

Множество истинности дизъюнкции предикатов есть объединение множеств истинности образующих ее предикатов, т.е. .

4.Импликацией предикатов А(х ) и В(х ), заданных на множестве Х, называется предикат А(х ) В(х ), который ложен при тех и только тех значениях переменной, при которых первый предикат обращается в истинное высказывание, а второй – в ложное.

Множество истинности импликации предикатов есть объединение множества истинности предиката В(х ) с дополнением к множеству истинности предиката А(х ), т.е.

5. Эквиваленцией предикатов А(х ) и В(х ), заданных на множестве Х, называется предикат , который обращается в истинное высказывание при всех тех и только тех значениях переменной, при которых оба предиката обращаются либо в истинные высказывания, либо в ложные высказывания.

Множество истинности эквиваленции предикатов есть пересечение множества истинности предиката с множеством истинности предиката .

Кванторные операции над предикатами

Предикат можно перевести в высказывание способом подстановки и способом «навешивание квантора».

Про числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 можно сказать: а) все данные числа простые; б) некоторые из данных чисел четные.

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

Если из предложения «а» убрать слово «все», а из предложения «б» - слово «некоторые», то получим следующие предикаты: «данные числа простые», «данные числа нечетные».

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

Различают два основных вида кванторов: квантор общности и квантор существования.

Термины «всякий», «любой», «каждый» носят название – квантор всеобщности. Обозначается .

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

В примере 1 для R 1 область определения: , множество значений - . Для R 2 область определения: , множество значений: .

Во многих случаях удобно использовать графическое изображение бинарного отношения. Оно осуществляется двумя способами: с помощью точек на плоскости и с помощью стрелок.

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

18. Способы задания бинарных отношений.

Всякое подмножество декартова произведения A×B называется бинарным отношением, определенным на паре множеств A и B (по латыни «бис» обозначает «дважды»). В общем случае по аналогии с бинарными можно рассматривать и n-арные отношения как упорядоченные последовательностиn элементов, взятых по одному из n множеств.

Для обозначения бинарного отношения применяют знак R. Поскольку R- это подмножество множества A×B, то можно записать R⊆A×. Если же требуется указать, что (a, b) ∈ R, т. е. между элементами a ∈ A и b ∈ B существует отношение R, то пишут aRb.

Способы задания бинарных отношений:

1. Это использование правила, согласно которому указываются все элементы, входящие в данное отношение. Вместо правила можно привести список элементов заданного отношения путем непосредственного их перечисления;

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

На (рисунке 1.16) изображена координатная сетка для множеств. Точкам пересечения трех вертикальных линий с шестью горизонтальными соответствуют элементы множества A×B. Кружочками на сетке отмечены элементы отношения aRb, где a ∈ A и b ∈ B, R обозначает отношение «делит».

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

3. Способ задания отношений с помощью сечений используется реже, поэтому рассматривать его не будем.

19. Рефлексивность бинарного отношения. Пример.

В математике бинарное отношение на множестве называется рефлексивным, если всякий элемент этого множества находится в отношении с самим собой.

Свойство рефлексивности при заданных отношениях матрицей характеризуется тем, что все диагональные элементы матрицы равняются 1; при заданных отношениях графом каждый элемент имеет петлю - дугу (х, х).

Если это условие не выполнено ни для какого элемента множества, то отношение называется антирефлексивным.

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

Формально антирефлексивность отношения определяется как: .

Если условие рефлексивности выполнено не для всех элементов множества, говорят, что отношение нерефлексивно.

©2015-2019 сайт
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-12