Операции над высказываниями и предикатами. Таблицы истинности
п.1. Отрицание
Расшифровка первого правила: высказывание «неверно, что для любого x выполняется A(x)» совпадает с высказыванием «найдётся x, для которого A(x) не выполняется».
Расшифровка второго правила: высказывание «неверно, что найдётся x, для которого выполняется A(x)» совпадает с высказыванием «для любого x A(x) не выполняется».
п.2. Конъюнкция
Обозначение конъюнкции A ∧ B, читается «А и В». Таблица истинности:
С точки зрения операций над множествами, конъюнкция аналогична пересечению двух множеств (см. §10 справочника для 8 класса).
С точки зрения записи условий, конъюнкция аналогична системе с фигурной скобкой.
п.3. Дизъюнкция
Обозначение дизъюнкции A ∨ B, читается «А или В». Таблица истинности:
С точки зрения операций над множествами, дизъюнкция аналогична объединению двух множеств (см. §10 справочника для 8 класса).
п.4. Импликация
Обозначение импликации A → B, читается «если A, то B».
Высказывание A называют «посылкой», а высказывание B – «заключением».
Значение импликации зависит от порядка высказываний.
Таблица истинности:
п.5. Эквиваленция
Обозначение эквиваленции A ↔ B, читается «A то же самое, что B» или «A эквивалентно B».
Таблица истинности:
п.6. Законы де Моргана
Докажем эквивалентность с помощью таблиц истинности:
Мы видим, что итоговые столбцы слева и справа полностью совпадают.
Значит, высказывания эквивалентны.
Докажем эквивалентность с помощью таблиц истинности:
Высказывания слева и справа эквивалентны.
Не путайте эквиваленцию и эквивалентность.
Эквиваленция – это логическая операция с 0 или 1 на выходе, в зависимости от исходных А и В.
Эквивалентность(равносильность) – это отношение, при котором эквиваленция A ↔ B истинна при всех значениях логических переменных на области определения. Тогда A ⇔ B (пишут также A=B, A≡B, A
B).
Если A ⇔ B, то каждое из предложений является и необходимым и достаточным условием для другого предложения; используются словосочетания «необходимо и достаточно», «равносильно».
п.7. Алгоритм доказательства эквивалентности высказываний с помощью таблиц истинности
Например:
Докажем следующее свойство:
Результат какой логической операции будет истинным тогда когда оба высказывания равнозначны
Прежде всего, начнем с разбора названия самого предмета, а именно выясним, каково значение алгебры, логики, а затем алгебры логики.
Алгебра – это раздел математики, предназначенный для описания действий над переменными величинами, которые принято обозначать строчными буквами латинского алфавита – а, b, x, y и т.д. Действия над переменными величинами записываются в виде математических выражений.
Термин «логика» происходит от древнегреческого “logos”, означающего «слово, мысль, понятие, рассуждение, закон».
Алгеброй логики называется аппарат, который позволяет выполнять действия над высказываниями.
Алгебру логику называют также алгеброй Буля, или булевой алгеброй, по имени английского математика Джорджа Буля, разработавшего в XIX веке ее основные положения. В булевой алгебре высказывания принято обозначать прописными латинскими буквами: A, B, X, Y. В алгебре Буля введены три основные логические операции с высказываниями: Сложение, умножение, отрицание. Определены аксиомы (законы) алгебры логики для выполнения этих операций. Действия, которые производятся над высказываниями, записываются в виде логических выражений.
Логические выражения могут быть простыми и сложными.
Простое логическое выражение состоит из одного высказывания и не содержит логические операции. В простом логическом выражении возможно только два результата — либо «истина», либо «ложь».
Сложное логическое выражение содержит высказывания, объединенные логическими операциями. По аналогии с понятием функции в алгебре сложное логическое выражение содержит аргументы, которыми являются высказывания.
В качестве основных логических операций в сложных логических выражениях используются следующие:
• НЕ (логическое отрицание, инверсия);
• ИЛИ (логическое сложение, дизъюнкция);
• И (логическое умножение, конъюнкция).
Логическое отрицание является одноместной операцией, так как в ней участвует одно высказывание. Логическое сложение и умножение — двуместные операции, в них участвует два высказывания. Существуют и другие операции, например операции следования и эквивалентности, правило работы которых можно вывести на основании основных операций.
Все операции алгебры логики определяются таблицами истинности значений. Таблица истинности определяет результат выполнения операции для всех возможных логических значений исходных высказываний. Количество вариантов, отражающих результат применения операций, будет зависеть от количества высказываний в логическом выражении, например:
Операция НЕ — логическое отрицание (инверсия)
Логическая операция НЕ применяется к одному аргументу, в качестве которого может быть и простое, и сложное логическое выражение. Результатом операции НЕ является следующее:
• если исходное выражение истинно, то результат его отрицания будет ложным;
• если исходное выражение ложно, то результат его отрицания будет истинным.
Для операции отрицания НЕ приняты следующие условные обозначения:
Результат операции отрицания НЕ определяется следующей таблицей истинности:
| A | не А |
| 0 | 1 |
| 1 | 0 |
Результат операции отрицания истинен, когда исходное высказывание ложно, и наоборот.
Приведем примеры отрицания.
1. Высказывание «Земля вращается вокруг Солнца» истинно. Высказывание «Земля не вращается вокруг Солнца» ложно.
3. Высказывание «4 — простое число» ложно. Высказывание «4 — не простое число» истинно.
Принцип работы переключателя настольной лампы таков: если лампа горела, переключатель выключает ее, если лампа не горела — включает ее. Такой переключатель можно считать электрическим аналогом операции отрицания.
Операция ИЛИ — логическое сложение (дизъюнкция, объединение)
Логическая операция ИЛИ выполняет функцию объединения двух высказываний, в качестве которых может быть и простое, и сложное логическое выражение. Высказывания, являющиеся исходными для логической операции, называют аргументами. Результатом операции ИЛИ является выражение, которое будет истинным тогда и только тогда, когда истинно будет хотя бы одно из исходных выражений.
Применяемые обозначения: А или В, А V В, A or B.
Результат операции ИЛИ определяется следующей таблицей истинности:
| A | B | А или B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Результат операции ИЛИ истинен, когда истинно А, либо истинно В, либо истинно и А и В одновременно, и ложен тогда, когда аргументы А и В — ложны.
Приведем примеры логического сложения.
1. Рассмотрим высказывание «В библиотеке можно взять книгу или встретить знакомого». Это высказывание формально можно представить так: С = А V В, где высказывание А — «В библиотеке можно взять книгу», а В — «В библиотеке можно встретить знакомого». Объединение этих высказываний при помощи операции логического сложения означает, что события могут произойти как отдельно, так и одновременно.
2. Рассмотрим высказывание «Знания или везение — залог сдачи экзаменов». «Успешно сдать экзамен может тот, кто все знает, или тот, кому повезло (например, вытянут единственный выученный билет), или тот, кто все знает и при этом выбрал «хороший» билет.
Кто хоть однажды использовал елочную гирлянду с параллельным соединением лампочек, знает, что гирлянда будет светить до тех пор, пока цела хотя бы одна лампочка. Логическая операция ИЛИ чрезвычайно схожа с работой подобной гирлянды, ведь результат операции ложь только в одном случае — когда все аргументы ложны.
Операция И — логическое умножение (конъюнкция)
Логическая операция И выполняет функцию пересечения двух высказываний (аргументов), в качестве которых может быть и простое, и сложное логическое выражение. Результатом операции И является выражение, которое будет истинным тогда и только тогда, когда истинны оба исходных выражения.
Применяемые обозначения: А и В, А ⋀ В, A & B, A and B.
Результат операции И определяется следующей таблицей истинности:
| A | B | А и B |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Результат операции И истинен тогда и только тогда, когда истинны одновременно высказывания А и В, и ложен во всех остальных случаях.
Приведем примеры логического умножения.
1. Рассмотрим высказывание «Умение и настойчивость приводит к достижению цели». Достижение цели возможно только при одновременной истинности двух предпосылок — умения И настойчивости.
Логическую операцию И можно сравнить с последовательным соединением лампочек в гирлянде. При наличии хотя бы одной неработающей лампочки электрическая цепь оказывается разомкнутой, то есть гирлянда не работает. Ток протекает только при одном условии — все составляющие цепи должны быть исправны.
Операция «ЕСЛИ-ТО» — логическое следование (импликация)
Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием из этого условия.
если А, то В; А влечет В; if A then В; А-> В.
Результат операции следования (импликации) ложен только тогда, когда предпосылка А истинна, а заключение В (следствие) ложно.
Приведем примеры операции следования.
1. Рассмотрим высказывание «Если идет дождь, то на улице сыро». Здесь исходные высказывания «Идет дождь» и «На улице сыро». Если не идет дождь и не сыро на улице, результат операции следования — истина. На улице может быть сыро и без дождя, например, когда прошла поливочная машина или дождь прошел накануне. Результат операции ложен только тогда, когда дождь идет, а на улице не сыро.
a) А — ложно, В — ложно (1-я строка таблицы истинности). Можно найти такие числа, для которых истиной является высказывание «если А — ложно, то и В — ложно». Например, х = 4, 17, 22.
b) А — ложно, В — истинно (2-я строка таблицы истинности). Можно найти такие числа, для которых истиной является высказывание «если А — ложно, то В — истинно». Например, х = б, 12, 21.
c) А — истинно, В — ложно (3-я строка таблицы истинности). Невозможно найти такие числа, которые делились бы на 9, но не делились на 3. Истинная предпосылка не может приводить к ложному результату импликации.
d) А — истинно, В — истинно (4-я строка таблицы истинности). Можно найти такие числа, для которых истиной является высказывание «если А — истинно, то и В — истинно». Например, х = 9, 18, 27.
Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)
Применяемое обозначение: А = В, А
B
Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны.
Приведем примеры операции эквивалентности:
1. День сменяет ночь тогда и только тогда, когда солнце скрывается за горизонтом;
2. Добиться результата в спорте можно тогда и только тогда, когда приложено максимум усилий.
8 класс. Урок Логические операции. Построение таблиц истинности-09.11.2021, 10.11.2021
Перед уроком
Добрый день! Входите, садитесь. Сегодня мы продолжим тему «Логические операции» и более подробно поговорим про «Построение таблиц истинности».
Сегодня вам необходимо:
1) Посмотреть видеоурок
2) Составить конспект
3) Пройти тест на оценку
Тема урока «Логические операции. Построение таблиц истинности»
Добрый день! Мы продолжим изучение темы «Логические операции» — §1.3. в учебнике.
После просмотра проведите зарядку для глаз.
Самое главное:
Сегодня мы узнаем, какие существуют правила для построения таблицы истинности для логических выражений, в которых количество логических операций больше одной. Также познакомимся со свойствами логических операций.
Прежде всего давайте вспомним логические операции, которые мы с вами изучали на прошлом уроке. К ним относятся инверсия, конъюнкция и дизъюнкция. Рассмотрите внимательно таблицу с обозначениями логических операций, которые мы будем использовать в дальнейшем.
Конъюнкция – это логическая операция, которая объединяет два высказывания в одно новое, которое будет являться истинным тогда и только тогда, когда оба исходных высказывания истинны.
Дизъюнкция – это логическая операция, которая объединяет два высказывания в одно новое, которое будет являться ложным тогда и только тогда, когда ложны оба исходных высказывания.
Инверсия – это логическая операция, которая преобразует исходное высказывание в новое, значение которого противоположно исходному.
Логические выражения могут состоять из более чем двух логических операций. В тоже время, для любых логических выражений можно построить таблицу истинности, в которой мы сможем увидеть, какие значения принимает выражение. Логические операции выполняются в следующем порядке: инверсия, конъюнкция и дизъюнкция.
Итак, для начала рассмотрим, какие действия следует выполнить для построения таблицы истинности:
Мы с вами знаем, что переменные обозначаются с помощью букв латинского алфавита.
2. Подсчитать общее число логических операций в выражении.
Количество логических операций: 2
То есть нам нужно сосчитать сколько в нашем выражении инверсий, конъюнкций и дизъюнкций.
3. Установить последовательность выполнения логических операций с учётом скобок и приоритетов. Как мы с вами знаем, сначала выполняются операции в скобках, затем инверсия, конъюнкция и дизъюнкция.
4. Определить число столбцов в таблице: число переменных плюс число операций. То есть нам нужно сложить количество переменных и логических операций. Мы получим число столбцов в таблице.
Количество столбцов: 5.
5. Заполнить шапку таблицы, включив в неё переменные и операции в соответствии с последовательностью, установленной в пункте три. То есть мы сначала пишем в шапке таблицы все наши переменные. Затем операции в порядке их следования.
6. Определить число строк в таблице (не считая шапки таблицы):
m – это количество строк. n – число переменных в выражении. То есть, если наше логическое выражение будет состоять, например, из трёх переменных, то количество строк m = 23 = 8. Шапка не входит в количество этих строк.
7. Выписать наборы входных переменных с учётом того, что они представляют собой ряд целых n-разрядных двоичных чисел от 0 до 2^n – 1. Здесь мы должны написать все возможные входные переменные, как мы делали при построении таблиц истинности.
8. Провести заполнение таблицы по столбцам, выполняя логические операции в соответствии с установленной последовательностью. То есть произвести логические операции с входными данными в зависимости от логической операции.
А теперь давайте разберёмся на примере. Необходимо построить таблицу истинности для следующего логического выражения: (A & B) & A v B.
Исходя из первого пункта плана построения таблицы истинности, нам нужно посчитать число переменных в выражении. Их у нас две: n = 2. А и B.
Общее число логических операций 3.
А сейчас давайте установим последовательность выполнения логических операций. Сначала будут выполняться логическая операция в скобках – конъюнкция. То есть первым будет выполнятся действие А & B.
Вторая логическая операция снова конъюнкция. И третья логическая операция – дизъюнкция.
Так как у нас 2 переменных и 3 логических операции, значит столбцов у нас будет 5. Так как в четвёртом пункте указан именно такой способ подсчёта столбцов.
Заполним теперь шапку таблицы. Сначала будут идти переменные А и B. Затем логические операции в порядке их выполнения.
Определимся с количеством строк. Нам дана формула для вычисления строк:
Теперь необходимо выписать наборы входных данных. То есть заполнить два первых столбца.
Нам необходимо заполнить столбцы числами от 0 до 3. Так как все операции мы производим в двоичной системе счисления, то представим числа от 0 до 3 в двухразрядном двоичном коде. Получим следующие числа:
00 это 0
01 это 1
10 это 2
11 это 3
Теперь занесём эти числа в первый и второй столбцы. По одной цифре в ячейку.
А сейчас заполним все остальные столбцы. Первая операция – конъюнкция. Данные будем вносить в третий столбец. Прежде, чем начать заполнение таблицы истинности вспомним правило для конъюнкции: новое высказывание будет истинно тогда и только тогда, когда исходные высказывания истинны. Значит в четвёртой строке для данного столбца будет стоять 1, так как это единственный случай, когда истинны оба исходных высказывания, значит и новое будет истинно. В первых трёх строках этого же столбца будут стоять нули, так как в первой строке ложны оба высказывания, во второй – высказывание А, а в третьей – высказывание B.
Переходим к четвёртому столбцу. Здесь снова логическая операция – конъюнкция. А данные мы будем брать из первого и третьего столбцов. И снова 1 будет стоять только в четвёртой строке для данного столбца, так как оба наших высказывания – истинны. В остальных – будут стоять нули.
Нам осталось заполнить последний, пятый столбец. Логическая операция – дизъюнкция. Правило звучит следующим образом: новое высказывание будет ложно тогда и только тогда, когда ложны исходные высказывания. Рассматривать будем второй и четвёртый столбцы. Значит в первой и третьей строках для данного столбца будут стоять нули, так как оба выражения в данной ситуации ложны. В остальных строках этого же столбца будут стоять единицы.
Мы построили таблицу истинности для нашего логического выражения. Следует обратить внимание, что данные в последнем столбце совпали с данными столбца B.
В такой ситуации говорят, что логическое выражение (A & B) & A v B равносильно логической переменной B.
Задание:
Прочтите параграф 1.3., стр 29-30 и сделайте конспект (он вам очень пригодится). Ответьте на вопрос после параграфа письменно стр. 39 №8.
Тест. Перед тестом обязательно прорешать номера после параграфа. Выполните тест на оценку https://videouroki.net/tests/48622657/
Внимание, важно! Когда будете вводить фамилию, имя и класс – вводите, пожалуйста, настоящие. В конце теста вы увидите свою оценку. Результат теста автоматически отправляется мне. При этом фиксируется время прохождения теста и адрес. Учтите, если вы проходите тест несколько раз, я засчитаю только первый. Поэтому будьте внимательны! На выполнение задания у вас неделя.
Итак, тема, которую мы начали изучать не самая простая. Если вам было что-то непонятно, то на youtube есть очень много видео по этой теме, посмотрите. И, конечно, я всегда готова ответить на ваши вопросы.
Решение письменного номера всем присылать не нужно, я могу попросить некоторых из вас «сдать» тетради на проверку (т.е. прислать фотографии домашней работы).
Операции над высказываниями.
Конъюнкцией высказываний А и В называется высказывание, читаемое: «А и В», которое истинно в единственном случае, когда высказывания А и В истинны одновременно.
Дизъюнкцией высказываний А и В называется высказывание, читаемое: «А или В», которое ложно в единственном случае, когда оба высказывания ложны одновременно.
Импликацией высказываний А и В называется высказывание, читаемое: «Если А, то В», которое ложно в единственном случае, когда высказывание А истинно и высказывание В ложно.
Эквиваленцией высказываний А и В называется высказывание, читаемое: «А тогда и только тогда, когда В», которое истинно в двух случаях, когда высказывания А и В истинны одновременно, когда высказывания А и В ложны одновременно.
Отрицанием высказывания А называется высказывание, читаемое «не А», которое ложно, когда А истинно и истинно, когда высказывание А ложно.
Обозначение операций над высказываниями.
Обозначение, запись, чтение высказываний. Логическое значение высказывания.
Если известно по условию задачи, какое именно повествовательное предложение названо или обозначено символом А, то А – логическая константа.
Например: А : «Декабрь – зимний месяц». А – логическая константа.
Если неизвестно какое повествовательное предложение обозначено этим символом, то А – логическая переменная. Из логических переменных, символов бинарных и унарных операций, скобок составляются выражения с логическими переменными. Каждая логическая переменная является элементарным выражением с логической переменной. Если в записи выражения имеется хотя бы один символ операции, то оно называется составным.
Два выражения с логическими переменными называются равносильными, если при каждом наборе логических значений переменных в них входящих, эти выражения принимают одно и то же значение.
Если выражения F1 и F2 равносильны, то пишут: F1≡ F2.
Если при каждом наборе логических значений переменных, входящих в данное выражение, оно принимает ложное значение, то данное выражение называется тождественно-ложным или противоречием. Тождественно – ложное выражение F обозначают: F≡0.
Если при каждом наборе логических значений переменных, входящих в данное выражение, оно принимает истинное значение, то данное выражение называется тождественно-истинным или тавтологией. Тождественно – истинное выражение F обозначают: F≡1.
Не всякое выражение является тождественно–истинным или тождественно-ложным. Если существуют наборы, при которых выражение принимает истинное значение, и существуют наборы, при которых оно принимает ложное значение, то выражение не является ни тождественно-истинным, и ни тождественно-ложным.
Свойства операций над высказываниями.
Каждое свойство операций над высказываниями является равносильностью двух выражений с логическими переменными. Будем называть основные свойства основными равносильностями.
Каждая сформулированная равносильность доказывается с помощью таблицы истинности.
