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

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

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

Задача 6.1. Известно, что высказывание $ \displaystyle AB$ ложно, а высказывание $ \displaystyle A \to B $ истинно. Определить значение истинности высказывания $ \displaystyle B \to A’ $, если известно, что его можно однозначно определить, используя эти данные.

Решение. Предположим, что это высказывание ложно:

$ \displaystyle B \to A’=0 $.

Почему мы предположили ложность, а не истинность данной импликации? Причина очень проста: импликация ложна только в одном случае. Если это предположение не будет противоречить условию задачи, то оно верно, так как значение истинности всякого высказывания — это ложь или истина. Согласно определению импликации, она ложна тогда и только тогда, когда посылка истинна, а заключение ложно:

$ \displaystyle B= 1$, $ \displaystyle A’=0 $.

В силу определения отрицания, оно ложно тогда и только тогда, когда само высказывание истинно:

$ \displaystyle A=1 $.

Но в этом случае, учитывая определения импликации и конъюнкции,

$ \displaystyle A \to B=1 $, $ \displaystyle A B=1 $.

Однако по условию задачи последнее высказывание имеет значение истинности «ложь». Получили противоречие. Значит, высказывание $ \displaystyle B \to A’ $ истинно.

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

$ \displaystyle AB=0 $,

то, согласно определению конъюнкции, возможны следующие варианты распределения истинностных значений высказываний $ \displaystyle A $ и $ \displaystyle B $:

1) $ \displaystyle A=B=0 $;

3) $ \displaystyle A=1 $, $ \displaystyle B=0 $.

Поскольку

$ \displaystyle A \to B=1 $,

то, согласно определению импликации, получаем, что значения истинности высказываний $ \displaystyle A $ и $ \displaystyle B $ могут быть такими:

1) $ \displaystyle A=B=0 $;

2) $ \displaystyle A=0 $, $ \displaystyle B=1 $;

3) $ \displaystyle A=B=1 $.

Условия $ \displaystyle A=1 $, $ \displaystyle B=0 $ и $ \displaystyle A=B=1 $ несовместимы, так как любое высказывание либо истинно, либо ложно. Остаются первые два варианта. Проверим их, используя определения импликации и отрицания:

1) $ \displaystyle B \to A’=0 \to 0’=0 \to 1=1 $;

2) $ \displaystyle B \to A’=1 \to 0’=1 \to 1 =1 $.

В обоих случаях высказывание $ \displaystyle B \to A’ $ имеет значение истинности «истина».

Очевидно, что первый способ решения настоящей задачи гораздо короче, чем второй.

Выяснить, достаточно ли данных, чтобы определить значение истинности высказывания

Задача 6.2. Пусть высказывание $ \displaystyle A \to B $ ложно. Достаточно ли этого, чтобы определить значение истинности высказывания $ \displaystyle (B \to (A \to C)) \vee (B’ \to C) $? Если достаточно, то указать это значение. Если не достаточно, то показать на примерах, что возможны оба истинностных значения.

Решение. Поскольку

$ \displaystyle A \to B=0 $,

то, согласно определению импликации,

$ \displaystyle A=1$, $ \displaystyle B=0 $.

Значит, импликация $ \displaystyle B \to (A \to C) $ истинна, так как её посылка ложна (какими бы ни были значения истинности высказываний $ \displaystyle A $ и $ \displaystyle C $). Следовательно, учитывая определение дизъюнкции, высказывание $ \displaystyle (B \to (A \to C)) \vee (B’ \to C) $ имеет значение истинности «истина».

Задача 6.3. Пусть известно, что высказывание $ \displaystyle AB $ истинно. Возможно ли, используя эти данные, определить значение истинности высказывания $ \displaystyle (AB) \to ((ABC’) \vee (A’BC))$ ? Если возможно, то указать это значение. В противном случае показать на примерах, что высказывание может быть как истинным, так и ложным.

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

$ \displaystyle A=B=1 $.

Значит, импликация $ \displaystyle (AB) \to ((ABC’) \vee (A’BC))$ истинна, если её заключение истинно, и ложна в противном случае (в силу определения данной логической связки). Рассмотрим дизъюнкцию $ \displaystyle (ABC’) \vee (A’BC) $. Известно, что

$ \displaystyle A=B=1 $.

Тогда, согласно определению отрицания $ \displaystyle A’=0 $. Если $ \displaystyle C=0 $, то $ \displaystyle C’=1 $. Следовательно, согласно определению, конъюнкция $ \displaystyle ABC’ $ истинна, а конъюнкция $ \displaystyle A’BC $ ложна. Значит, дизъюнкция $ \displaystyle (ABC’) \vee (A’BC) $ истинна. Если $ \displaystyle C=1 $, то $ \displaystyle C’=0 $. Следовательно, высказывания $ \displaystyle ABC’ $ и $ \displaystyle A’BC $ ложны. Тогда и дизъюнкция $ \displaystyle (ABC’) \vee (A’BC) $ ложна. Итак, высказывание $ \displaystyle (AB) \to ((ABC’) \vee (A’BC))$ имеет значение истинности «ложь» при

$ \displaystyle C=1 $

и «истина» при

$ \displaystyle C=0 $.

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

Выяснить, существуют ли высказывания с данными значениями истинности

Задача 6.4. Пусть высказывание $ \displaystyle A \vee B’ $ и $ \displaystyle B \to (A \vee C) $ имеет значение истинности «ложь», а высказывание $ \displaystyle C’ \to B’ $ имеет значение истинности «истина». Существуют ли такие высказывания $ \displaystyle A $, $ \displaystyle B$ и $ \displaystyle C $?

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

$ \displaystyle A=B’=0 $.

Следовательно, учитывая определения отрицания,

$ \displaystyle B=1 $.

Рассмотрим импликацию

$ \displaystyle B \to (A \vee C) $.

По условию задачи она ложна. Это возможно тогда и только тогда, когда

$ \displaystyle B=1 $, $ \displaystyle A \vee C =0 $.

Значит, в силу определения дизъюнкции,

$ \displaystyle A=C=0 $.

Следовательно,

$ \displaystyle C’ \to B’=0′ \to 1’=1 \to 0=0 $.

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

Пример 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. Для каждого из помещенных ниже высказываний определите, достаточно ли приведенных сведений, чтобы установить его логическое значение. Если достаточно, то укажите это значение. Если недостаточно, то покажите, что возможны и одно, и другое истинностные значения:

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

Пример 1. Установить истинность высказывания · С Решение. В состав сложного высказывания входят 3 простых высказывания: А, В, С.

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

А	В	С		А+		· С
0	0	0	1	1	0	0
0	0	1	1	1	0	0
0	1	0	0	0	1	0
0	1	1	0	0	1	1
1	0	0	1	1	0	0
1	0	1	1	1	0	0
1	1	0	0	1	0	0
1	1	1	0	1	0	0

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

Вы также можете найти интересующую информацию в научном поисковике Otvety.Online. Воспользуйтесь формой поиска:

Еще по теме 1. Установление истинности сложных высказываний.:

1. 29. Проблема разрешимости в алгебре высказываний(АВ). Алгоритмы проверки формул алгебры высказываний на тождественную истинность: составление таблицы истинности, выполнение равносильных преобразований (анализ КНФ), алгоритм редукции, алгоритм Квайна. Преимущества и недостатки указанных методов.
2. Вопрос 6. Исчисление высказываний. Аксиомы. Правило вывода. Вывод. Тождественная истинность выводимых формул (доказать). Непротиворечивость исчисления высказываний. Теорема о полноте исчисления высказываний. Проблема разрешимости. Исчисление высказываний. Проблема разрешимости

Урок №2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Этапы урока

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

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

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

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

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

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

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

Ход урока

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

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

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

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

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

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

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

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

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

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

2.

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

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

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

6.

7.

(Примеры 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”

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

6.

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

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

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

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

Итог урока:

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

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

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