ТОЖДЕСТВЕННО ИСТИННЫЕ И ТОЖДЕСТВЕННО ЛОЖНЫЕ ВЫСКАЗЫВАНИЯ
· приоритет логических операций;
· тождественно истинные и тождественно ложные операции;
· основные законы алгебры логики;
· доказательство логических законов;
· простейшие преобразователи информации;
Если сложное высказывание истинно для всех значений входящих в него переменных, то такое высказывание называется ТОЖДЕСТВЕННО ИСТИННЫМ или тавтологией (обозначается константой 1).
Все математические, физические и др. законы являются тавтологиями. Например: (а+b) 2 = a 2 + 2ab + b 2
Прогноз погоды на завтра может быть, например, таким: «Дождь будет или дождя не будет». Такое предсказание будет всегда истинным, хотя вряд ли кого устроит. Его математическая запись:
(по закону исключенного третьего всегда должно быть истинным либо суждение, либо его отрицание).
Проверить, является ли сложное высказывание тождественно истинным, можно по таблице истинности.
Если сложное высказывание ложно при всех значениях входящих в него переменных, то такое высказывание называется ТОЖДЕСТВЕННО ЛОЖНЫМ (обозначается константой 0 ).
(по закону противоречия: не могут быть одновременно истинны утверждение и его отрицание.)
Если значения сложных высказываний совпадают при всех возможных значениях входящих в них переменных, то такие высказывания называют РАВНОСИЛЬНЫМИ, ТОЖДЕСТВЕННЫМИ, ЭКВИВАЛЕНТНЫМИ
ОСНОВНЫЕ ЗАКОНЫ (РАВНОСИЛЬНОСТИ) АЛГЕБРЫ ЛОГИКИ
· приоритет логических операций;
· тождественно истинные и тождественно ложные операции;
· основные законы алгебры логики;
· доказательство логических законов;
· простейшие преобразователи информации;
При решении логических задач часто приходится упрощать формулы. Упрощение формул в булевой алгебре производится на основе эквивалентных преобразований, опирающихся на основные законы.
1.1. Закон тождества:
— всякая мысль тождественна самой себе, то есть «А есть А», где А – любое высказывание.
2. Закон исключенного третьего:
— в один и тот же момент времени высказывание может быть либо истинным, либо ложным, третьего не дано. Истинно либо А, либо не А.
НАПРИМЕР. «Число 123 либо четное, либо нечетное, третьего не дано».
Закон исключенного третьего не является законом, признаваемым всеми логиками в качестве универсального закона логики. Этот закон применяется там, где познание имеет дело с жесткой ситуацией: либо-либо, истина-ложь. Там же где встречается неопределенность (например, в рассуждениях о будущем), закон исключенного третьего часто не может быть применен.
Рассмотрим следующее высказывание: «Это предложение ложно». Оно не может быть истинным, потому, что оно утверждает, что оно ложно. Но оно не может быть и ложным, потому что тогда оно было бы истинным. Это высказывание не истинно и не ложно, а потому нарушается закон исключенного третьего.
«В одном городе парикмахер стрижет волосы всем жителям, кроме тех, кто стрижет себя сам. Кто стрижет волосы парикмахеру?»
В нашей формальной системе нет возможности ввести такое ссылающееся само на себя истолкование, поэтому мы не можем выразить все возможные мысли и доводы.
3. Закон непротиворечия:
Именно эта формула часто используется при упрощении сложных логических выражений.
Иногда этот закон формулируется так: два противоречащих друг другу высказывания не могут быть одновременно истинными.
ПРИМЕР. Е = «На Марсе есть жизнь и на Марсе жизни нет»
4. Закон двойного отрицания:
— если отрицать дважды некоторое высказывание, то в результате получается исходное высказывание.
Урок информатики по теме «Построение таблиц истинности для сложных логических выражений»
I. Организационный момент. Учащимся выдается лист с тематической разработкой по теме после самостоятельной работы (приложение1).
Записать условие, которое является истинным, когда точка с координатами (x;y) попадает в заштрихованные участки плоскости.
Рисунок 1
IV. Объяснение нового материала.
1. Найдите значения логических выражений:
2. Даны простые высказывания:
Определите истинность составных высказываний:
IV. Объяснение нового материала
Построение таблиц истинности для сложных высказываний
Для ответа на поставленный вопрос требуется знать значение истинности каждого простого высказывания, входящего в сложное. Но поскольку такого знания нет, то придется рассмотреть все возможные варианты.
Строится таблица истинности:
А
В
0
0
1
0
1
0
1
1
1
0
1
0
0
0
1
1
1
0
0
1
V. Закрепление изученного материала.
1. С помощью таблиц истинности доказать тождества:
А
В
0
0
1
1
1
0
1
1
0
1
0
1
1
0
0
1
0
1
0
1
1
0
0
1
0
1
0
1
0
1
1
1
0
0
0
1
0
0
1
0
2. Построив таблицу истинности сложного выражения , докажите, что оно является тождественно-ложным.
А
В
С
(1-я)
(2-я)
(3-я)
Итог
0
0
0
1
1
1
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
0
1
0
1
0
0
0
0
0
1
1
1
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
0
1
0
1
0
1
0
0
0
0
0
1
1
0
0
0
1
0
0
0
0
1
1
1
0
0
0
0
0
0
0
Выражение называется тождественно-ложным, если оно ложно при любых значениях простых высказываний, в него входящих.
Изучили: Правила определения значения истинности сложных высказываний путем построения таблиц истинности.
1. Доказать, что логическое выражение является тождественно-истинным или опровергнуть это утверждение.
Тождественно истинные, тождественно ложные и эквивалентные высказывания
Тождественно истинные, тождественно ложные и эквивалентные высказывания
Если высказывание истинно при всех значениях входящих в него переменных, то такое высказывание называется тождественно истинным или тавтологией (обозначается константой 1).
Например, высказывание Демократ — это человек, исповедующий демократические убеждения всегда истинно, т. е. является тавтологией.
Прогноз погоды на завтра может быть, например, таким:
Дождь будет или дождя не будет.
Такое предсказание будет всегда истинным, хотя вряд ли кого устроит. Его математическая запись:
Проверить, является ли сложное высказывание тождественно истинным, можно по таблице истинности.
Мы видим, что во многих случаях, когда трудно установить, верно ли мы рассуждаем, всегда ли будет истинно наше утверждение, удобно применять средства математической логики.
Если высказывание ложно при всех значениях входящих в него переменных, то такое высказывание называется тождественно ложным (обозначается константой 0).
Например, высказывание Сегодня среда, а это — второй день недели является тождественно ложным.
Тождественно ложным является и следующее высказывание: Компьютер включен, и компьютер не включен (выключен) Математическая запись его такова:
Если значения сложных высказываний совпадают на всех возможных наборах значений входящих в них переменных, то такие высказывания называют равносильными, или тождественными, или эквивалентн ым и.
Равносильность высказываний А и В записывается с помощью знака равенства (=):
Высказывания А и В равносильны (А = В) тогда и только тогда, когда их эквивалентность А В является тождественно истинным высказыванием.
В качестве примера рассмотрим два высказывания:
X= Не может быть, что Матроскин выиграл приз и отказался от него.
Y = Или Матроскин не отказался от приза, или не выиграл его.
Чтобы доказать равносильность (эквивалентность) сложных высказываний Х и Y, достаточно построить их таблицы истинности. Объединим эти две таблицы в одну:
Алгебра логики — раздел математики, изучающий высказывания с точки зрения их логических значений (истинности или ложности) и логических операций над ними. Иногда ее называют двоичной логикой или булевой алгеброй по имени английского математика Джорджа Буля.
Для удобства записи, используют обозначение результата через F, а логические высказывания через A (X) и B (Y). Так как возможных вариантов значений всего два, их можно обозначить через 0 (ложь, нет, false, no) и 1 (истина, да, true, yes).
Таблица истинности — табличное представление логической схемы (операции), в котором перечислены все возможные сочетания значений истинности входных сигналов (операндов) вместе со значением истинности выходного сигнала (результата операции) для каждого из этих сочетаний.
Логическое высказывание
Логическое высказывание — любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.
Тождественно истинные высказывания (тавтология)
Тождественно истинными называются высказывания, истинные при любых значениях входящих в него переменных.
Таким образом, такое высказывание всегда равно 1.
В качестве примеров можно привести высказывания, являющиеся разъяснением термина на основе его словообразования (авиабаза — место базирования авиационной техники). Или любое сложное высказывание, смысл которого сводится к формуле А \/ ¬A.
Тождественно ложные высказывания
Тождественно ложными называются высказывания, ложные при любых значениях входящих в него переменных.
Таким образом, такое высказывание всегда равно 0.
Важно, что большинство высказываний сводится к формуле А /\ ¬A.
Эквивалентные высказывания
Эквивалентными (тождественными или равносильными) называются высказывания, значения которых совпадают при любых значениях входящих в него переменных.
Логические операции
Логическое умножение (конъюнкция)
Представляет собой объединение нескольких логических выражений с помощью союза И. При практическом наборе на компьютере часто используют знаки прямого и обратного деления без пробела: /\
Таким образом, все значения должны быть истинными: И первое, И второе, И. При умножении логических операторов мы получим единицу только если все они будут равны единице:
A
B
F = A & B
0
0
0
0
1
0
1
0
0
1
1
1
Отсюда вытекает обратное следствие, упрощающее вычисления для конъюнкции: Если хотя бы одно значение ложно, то ложно и всё выражение.
Логическое сложение (дизъюнкция)
Представляет собой объединение логических выражений с помощью союза ИЛИ. Если при сложении результат становится больше нуля, то он выражается единицей. При практическом наборе на компьютере часто используют знаки обратного и прямого деления без пробела: \/
A
B
F = A \/ B
0
0
0
0
1
1
1
0
1
1
1
1
Отсюда вытекает обратное следствие, упрощающее вычисления для дизъюнкции: Если хотя бы одно значение истинно, то истинно и всё выражение.
Логическое отрицание (инверсия)
Представляет собой логическое выражение с добавленной в начале частицей НЕ. То есть операция всегда обращает значение в противоположное.
A
F = ¬A
0
1
1
0
Логическое следование (импликация)
Связывает два логических выражения с помощью оборота ЕСЛИ. ТО. Дополнительная операция, так как A → B = \/ B Кроме того, при построении высказывания могут использоваться выражения «из. следует», «. влечет».
A
B
F = A → B
0
0
1
0
1
1
1
0
0
1
1
1
В таблице хорошо видна практическая суть: импликация ложна только тогда, когда первое выражение истинно, а второе ложно.
При решении задач, в большинстве случаев требуется применение закона снятия импликации.
Логическое равенство (эквивалентность)
Образуется соединением двух логических выражений с помощью оборотов «тогда и только тогда», «необходимо и достаточно», «. равносильно. ». Поскольку мы видим здесь двойное следование (и вправо и влево), операцию иногда называют двойной импликацией. Дополнительная операция, так как A ↔ B = (A ∨ ) & ( ∨ B)
A
B
F = A ↔ B
0
0
1
0
1
0
1
0
0
1
1
1
Суть: эквивалентность ложна только тогда, когда выражения разные.
Законы алгебры логики
Те, кому лень учить эти законы, должны вспомнить алгебру, где знание нескольких способов преобразования позволяет решать очень сложные уравнения.
Строго говоря, это не законы, а теоремы. Но их доказательство не входит в программу изучения. Впрочем, доказательство обычно основывается на построении полной таблицы истинности.
Замечание. Знаки алгебры логики намеренно заменены на сложение и умножение.
№
Для ИЛИ
Для И
Примечание
1
A + 0 = A
A • 1 = A
Ничего не меняется при действии, константы удаляются
2
A + 1 = 1
A • 0 = 0
Удаляются переменные, так как их оценивание не имеет смысла
3
A + B = B + A
AB = BA
Переместительный (коммутативности)
4
A + = 1
Один из операторов всегда 1 (закон исключения третьего)
5
A • = 0
Один из операторов всегда 0 (закон непротиворечия)
6
A + A = A
A • A = A
Идемпотентности (NB! Вместо A можно подставить составное выражение!)
7
¬¬A = A
Двойное отрицание
8
(A+B)+C = A+( B+C)
(A•B)•C = A•(B•C)
Ассоциативный
9
(A+B)•C = = (A•C)+( B•C)
(A•B)+C = = (A+C)•( B+C)
Дистрибутивный
10
(A+B)•(¬A+B) = B
(A•B)+(¬A•B) = B
Склеивания
11
¬(A+B) = ¬A•¬ B
¬(A•B) = ¬A+¬ B
Правило де Моргана
12
A+(A•C) = A
A•(A+C) = A
Поглощение
13
A→B = ¬A+ B и A→B = ¬B→ ¬A
Снятие (замена) импликации
14
1) A↔B = (A•B)+(¬A•¬ B) 2) A↔B = (A + ¬B)•(¬A + B)
Снятие (замена) эквивалентности
Порядок решения логического выражения
В первую очередь надо учитывать, что порядок задается скобками.
Далее выполняются операции отрицания, конъюнкции, дизъюнкции, импликации, эквивалентности.
Построение таблиц истинности
Чтобы решить логическое выражение, необходимо построить таблицу истинности, описывающую ВСЕ возможные варианты значений переменных величин. В связи с тем, что мы используем булевы переменные (то есть имеющие только два значения: 0 и 1), количество вариантов легко сосчитать по формуле
где N — число переменных, а M — число строк в результирующей таблице.
Заполнение же значений фактически является последовательным вписыванием в каждой строке двоичных чисел. Для первой строки это будет 0 (00, 000. ), для второй — 1 (01, 001. ), а для последней — числа, состоящего из всех единиц. Выполнение этого несложного правила позволит не только избежать ошибок, но и облегчит решение, так как значения 0/1 будут подчиняться определенному порядку для каждой переменной.
Графическое решение числовых выражений по координатной прямой
Ряд заданий в алгебре логики основывается в использовании в качестве высказывания числового выражения. Например,
Хорошо видно, что выражение берется в скобки для однозначного восприятия. Прежде чем наносить значения на рисунок, следует избавиться от отрицания. В этом случае происходит замена знаков отношения на противоположные по схеме: ↔ ≤, = ↔ ≠.
В нашем примере мы получим
Нанесем два значения на координатную прямую и, учитывая логическое И, у нас должны совпасть оба условия. То есть на прямой это будет пересечение, обозначенное красным.
Возможные целочисленные ответы — 3, 4, 5.
Построение логического выражения по таблице истинности
Задача является противоположной стандартной.
При ее решении нужно построить дизъюнкцию для всех строк, равных 1, то есть составить выражение в дизъюнктивной нормальной форме (ДНФ).
Решение текстовых задач
На предыдущих этапах, в частности, изучались графический и табличный способы, которые невозможно, либо чрезмерно трудоемко использовать для сложных заданий. Также, решение задач путем рассуждений зачастую неэффективно.
Многие учащиеся очень расстраиваются, что, используя ранее эти способы, они тратили много времени на то, чтобы выработать стратегию, правильно понимать задание и т.п. А теперь их удается решить буквально за несколько секунд. Эта позиция неверна. Большинство подобных задач в реальной жизни не содержит достаточных сведений для решения средствами алгебры логики. Умение анализировать данные и находить «пробелы» в исходных данных — намного важнее.
При решении логической задачи средствами алгебры логики, необходимо выделить из текста логические условия и записать их в виде выражения.
Каждое высказывание оформляется в виде логической переменной. Чаще всего удобно вводить переменные, обозначенные русскими буквами и связанные с объектами, описанными в задаче: Иван — И, красный — К (или Кр, если переменная К уже введена для Коли) и т.п.
В большинстве случаев потребуется упрощение выражения с использованием законов алгебры логики.
В некоторых случаях удобно составить систему высказываний (аналогично системе уравнений) и, затем, решать уже её.
Логическое значение категорически рекомендуется записывать как 0 (ложь) или 1 (истина). Это поможет дифференцировать записи, а не спотыкаться о глупейшие варианты Л/И.
Введем обозначения для логических высказываний: Л — победит Ласточка; С — победит Стрела; Т — победит Тормоз. Запишем высказывания (высказывание Петра «Тормоз готовился очень тщательно» не содержит информации о месте и не может быть учтено):
Учитывая истинность предположений двух друзей и ложность третьего, запишем истинное высказывание, основанное на том, что неправ либо первый, либо второй, либо третий:
Затем упростим его за счет двойного отрицания, правила Моргана и убрав ненужные для первого члена скобки:
В оставшейся части сократим противоположные слагаемые (по закону исключения третьего)
Конечно, можно сразу сказать, что в произведении все три множителя должны быть равны единице, то есть: Л = 1, Т = 0, С = 0. Ответ: победителем скачек стала Ласточка.
Но можно сделать то же, построив таблицу истинности:
, докажите, что оно является тождественно-ложным.
является тождественно-истинным или опровергнуть это утверждение.
\/ B 
) & ( 