1. Тема №1. Высказывания в логике.

Основоположником формальной логики считается Аристотель (-384..-322гг.). Ученик Платона. Воспитатель Александра Македонского.

Высказывание – повествовательное предложение, в отношении которого имеет смысл говорить о его истинности либо ложности (Аристотель).

Примеры высказываний:

1. Число 10 чётно.
2. Число 10 нечётно.
3. У любого петуха есть крылья.
4. На улице холодно.
5. Шурик хочет конфетку.
6. Если очень захотеть, можно взять и полететь.
7. Я люблю хачапури.

Примеры не-высказываний:

1. Число называется положительным, если оно больше нуля.
2. На самом ли деле Шурик хочет конфетку?
3. Докажите, что 2*2=4.
4. Число х чётно.
5. Уходя, гасите свет.
6. Да здравствует Летающий Макаронный Монстр!
7. Сумма чисел 7 и Х равна 10.

Пример утверждения, об истинности либо ложности которого говорить невозможно: "Это утверждение ложно". Докажем это:

1. Допустим, что это утверждение ИСТИННО. В таком случае из него следует, что оно является ложным, что противоречит нашему предположению, след. оно неверно.
2. Допустим, что оно ЛОЖНО. В таком случае, на самом деле оно истинно. А в этом случае см.п.1. Опять противоречие, след. и это предположение неверно.

Это пример того, что формальная логика – ограниченный инструмент и рецепт выхода из ловушек, раставленных "формальными логиками" (пример: роман С.Лема "Навигатор Пиркс").

В логике мы не вникаем в смысл высказываний, а лишь изучаем формальные их связки с помощью т.н. "логических операций".

1. Рассмотрение таблицы истинности для импликации.

Пусть Х – высказывание "Петя гуляет", Y – высказывание "Коля делает уроки". Каждое из них может быть как истинным, так и ложным (рассматриваем в конкретный момент времени).

Можно сконструировать некое высказывание Z = X → Y: "Если Петя гуляет, то Коля делает уроки". Оно может быть также – истинным или ложным. Причём независимо от истинности и ложности высказываний X и Y.

В этом составном высказывании X называют "посылкой", а Y – "следствием". Данное высказывание говорит о двух вещах:

• Истинность ПОСЫЛКИ является достаточным условием для истинности СЛЕДСТВИЯ
• Истинность СЛЕДСТВИЯ является НЕОБХОДИМЫМ для истинности ПОСЫЛКИ.

В нашем примере. Если высказывание Z истинно, то это означает:

• Того факта, что Петя гуляет, ДОСТАТОЧНО, чтобы утверждать, что Коля делает уроки. Т.е. если X – истинно, то, по-любому, Y – истинно, без вариантов. Мы получаем 4 строку таблицы истинности. Но это если Z истинно (4 строка). А если ложно? Т.е. мы видим, что Петя – гуляет, но Коля уроков не делает. Что это означает? Только одно – исходное высказывание ложно (так мы получаем 3 строку таблицы).
• Но если мы видим, что Коля делает уроки, можем ли мы утверждать, что Петя гуляет? Наше составное высказывание об этом ничего не говорит. Следовательно, у нас нет никакой информации на этот счёт, и Петя может как гулять, так и нет. Это отражено в строках 4 и 2: при истинных Z и Y значение X может быть любым: как 0, так и 1. Поэтому в таких случаях говорят, что истинности СЛЕДСТВИЯ недостаточно для истинности посылки – нужна дополнительная информация.
• Однако мы можем заметить, что для того, чтобы точно знать, что Петя гуляет, НЕОБХОДИМО, чтобы Коля делал уроки. Иначе составное высказывание ложно. Отсюда следует вывод: если мы видим, что Коля уроков НЕ ДЕЛАЕТ (высказывание Y ложно), то мы можем однозначно заключить, что Петя НЕ ГУЛЯЕТ (высказывание X также обязано быть ложно). Это строка 1 таблицы.

Ещё раз рассмотрим строки таблицы 1 и 2. Они соответствуют ситуации, когда Z истинно, однако исходная посылка X ложна. Поскольку в связке ничего не говорится про эту ситуацию, то никакой информации об истинности следствия мы получить не можем, и значение Y может быть любым – как 0, так и 1, что и отражено в строках таблицы 1-2.

Их этого следует важный вывод: "Из истины следует истина, а из лжи – что угодно".

Посмотрим теперь на строки таблицы 1-2 слева направо, т.е. предположим, что мы пытаемся с помощью логики вывести новую информацию из исходных посылок X и Y, которые представляют собой "входную информацию". А Z – это наши логические выводы, которые мы собираемся использовать как собственно добытую информацию, истинность которой гарантирована логическими построениями.

Ситуация, когда X ложно, в таком случае приводит нас к значению "ИСТИНА" в любом случае. Таким образом, мы получаем заведомо ложную информацию под маской истины. Т.е. в этом смысле ложь на входе становится истиной на выходе. И от этого несоответствия формальных построений реальной жизни будут проистекать печальные последствия в виде лавины ошибок самоуправления и управления социальной суперсистеме. Отсюда следует, что лжи во спасение не бывает, и любая ложь всегда губительна для общества.

Домашнее задание №1 для всех классов:

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

Задание в классе.

1. В приведённых высказываниях выделите 2 простых, обозначьте их буквами и запишите все высказывания с помощью обозначений:

• Петя и Коля идут гулять  
• Петя идёт гулять, а Коля гулять не идёт
• Если Коля идёт гулять, то Петя гулять не идёт

2. С помощью таблицы логических операций составьте таблицы истинности для высказываний:

1. Y→X
2. X→(Y→X)
3. X ˅ Y  → (X & Y)
4. X & Z → (Y ˅ Z → X)

Для проверки можно использовать калькулятор http://tablica-istinnosti.ru/ru/

Решение 2.1:

Решение 2.2:

Решение 2.3:

Решение 2.4:

2. Законы алгебры высказываний

Аналогия: алгебра – операции над числами. Причём над произвольными числами, обозначаемыми буквами. Алгебра – это раздел математики, изучающий операции над множествами элементов произвольной природы. Элементарная алгебра – изучает операции над множеством действительных чисел. Формальная логика – алгебра высказываний, изучает операции над высказываниями произвольной природы, обозначая их буквами.

Пример из алгебры чисел: a+b = b+а. Это равенство, верное при любых значениях входящих в него переменных. Такие равенства называют тождествами.

Рассмотрим два высказывания: X и Y. Неважно, что они обозначают. Расмотрим 2 высказывания: А= X&Y (А="X и Y"), (А=X˄Y), (А=X*Y), (А=XY) и B=Y&X.

Построим таблицы истинности для высказываний А и В:

Сравнивая столбцы результатов, мы видим, что при любых значениях X и Y в них стоят одинаковые значения. Это означает, что высказывания А и B тождественны, т.е.  X&Y=Y&X. Мы получили переместительный закон алгебры высказываний (коммутативность). Аналогичным образом можно получить тождество X˅Y = Y˅X.

Ещё пример. Рассмотрим высказывания X→Y  и  X˅Y. Построим их Т.И.

Опять видим, что при столбцы совпадают, следовательно,  X→Y  =  X˅Y при любых значениях входящих в них высказываний X и Y.

Запишем таблицу основных законов алгебры высказываний.

Задание в классе: переписать таблицу в тетрадь.

Задания на дом (на декабрь): доказать законы методом составления таблиц истинности. Разобрать §31, задания к нему 1-9 в тетради.

Доп.задание для 10А(ФМ): найти 2 косяка в тексте учебника §31. Решить задачу 10 к нему.

Разберём пример на преобразование логических выражений:

(X & Y) ˅ Y =  (X & Y) ˅ (Y & 1) = (X & Y) ˅ (1 & Y) =

Вспомним закон №6:  (X ˅ Y) & Z = (X & Z) ˅ (Y & Z)

Обратим внимание, что в обозначениях закона надо аккуратно сделать подстановки:

= (X ˅ 1) & Y = 1 & Y = Y

Формула называется тавтологией, если она принимает значение 1 при любых значениях входящих в неё переменных.

Пример: X→X

Задание: найти тавтологии:

1. Если человек идиот, то это надолго.
2. Когда холодно, то идёт снег.
3. Если Вася хочет спать, то он хочет спать.
4. Нет покоя ни днём, ни ночью.
5. Если гражданин идиот, то он идиот.

Задания для сам.работы к §31, ответы:

7а,б) является

8а,б) не является      в) является

2. Построение логической формулы по заданной таблице истинности (СДНФ)

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

Например, пусть у нас имеются два высказывания X и Y. Известно также, что нужная нам логическая формула F задаётся следующей таблицей:

Можно заметить, что, поскольку F может принимать произвольные значения, то искомая функция должна содержать N составляющих (N = числу возможных комбинаций входных переменных), каждая из которых должна "отвечать" за свою строку заданной таблицы.

Предположим, что во всех ячейках колонки для F стояли бы нули (т.е. значения ЛОЖЬ). Очевидно, что в таком случае никаких составляющих в формуле не требовалось бы, а достаточно было бы написать F=0. Таким образом, можно подметить, что число составляющих в искомой формуле должно было равно числу единиц в колонке для F. В нашем примере это 1.

Рассмотрим строку 2 таблицы. Она требует того, что если (X=0 И Y=1), то F должно быть равна 1. Во всех остальных случаях – это к данной строке не относится.

Мы знаем функцию-"детектор единиц" – это операция И. Если X=0, то Х=1. Рассмотрев выражение Х & Y, мы увидем, что оно равно 1 только в том случае, когда (X=0 И Y=1), т.е. аккурат в том, что нам требуется.

Таким образом, формулируем предположение: наша таблица соответствует логической функции F =  Х & Y. Проверим это:

Задача решена.

А что изменится, если мы потребуем иную таблицу для F, например, такую:

Попробуем сформулировать некое правило:

1. Строки с F=0 отбрасываем
2. На каждую оставшуются строку пишем слагаемое – логическое умножение входящих в неё входных переменных, причём если в таблице переменная = 0, то её инвертируем.
3. Полученные слагаемые складываем логическим сложением (операция ИЛИ).

После вычёркивания строк с  F=0 у нас останется следующая таблица:

F = XY + XY

F = X*Y + X*Y

F = (X & Y) ˅ (X & Y)

Посмотрим теперь на формулу 22 законов алгебры высказываний и увидим, что мы только что вывели этот закон, позволяющий "раскрыть" операцию "сложение по модулю 2", или "ИСКЛЮЧАЮЩЕЕ ИЛИ".

Можно заметить, что нащупанный нами рецепт годится для составления ЛЮБЫХ логических формул по ЛЮБЫМ произвольно заданным таблицам для ЛЮБОГО количества входных переменных. Например, пусть надо построить логическую формулу F для трёх высказываний X, Y, Z следующим образом:

Вычёркивание строк с F=0 можно проделать мысленно, просто составляя слагаемые для строк с F=1:

F = X Y Z + X Y Z + X Y Z

F = (X&Y&Z) ˅ (X&Y&Z) ˅ (X&Y&Z)

F = X&Y&Z ˅ X&Y&Z ˅ X&Y&Z

Такая форма записи называнется "Совершенная дизъюнктивная нормальная форма", сокращенно СДНФ. Её можно определить так: "СДНФ – это логическая формула, удовлетворяющая следующим требованиям:

1. В ней используются ТОЛЬКО операции : ОТРИЦАНИЕ, И, ИЛИ.
2. Операция ОТРИЦАНИЕ применяется только к отдельным переменным (не к группам)
3. В каждую операцию И входят ВСЕ переменные (или их отрицания) ПО ОДНОМУ РАЗУ, причём в одном и том же порядке – получается набор дизъюнктивных выражений.
4. Операции ИЛИ объёдиняют (суммируют) полученные дизъюнктивные выражения."

В силу определённого порядка приоритетов скобки при записи СДНФ не требуются:

1. Сначала выполняются операции ОТРИЦАНИЯ
2. Конъюнкции (И) – порядок не важен.
3. Дизъюнкции (ИЛИ) – порядок не важен.

Домашнее задание: §32, зад.1-5.

Дополнительно для 10А(ФМ): зад.6.