Лекции по "Алгебре"

 

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

    Например: «Если треугольник имеет четыре стороны, то 2 +2 = 4». Такое высказывание в обыденной речи будет встречено с легким недоумением, но вы должны хорошо понимать, что это пример операции импликации. По определению, из ложной посылки «Если треугольник имеет четыре стороны», может следовать какое угодно заключение, и сложное высказывание будет истинным.

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

    Рассматривая  с такой точки зрения любые  два истинных высказывания, например «Дважды два четыре» и «Наполеон умер 5 мая 1821 года», равно как и любые два ложных высказывания вроде «Дважды два пять» и «Снег черен», трактуются как эквивалентные друг другу.

    Тема 1.4. Формулы алгебры логики

      Определение: Алфавитом называется любой непустой набор символов. Элементы этого набора называются символами алфавита.

      Определение: Словом в алфавите называется произвольная конечная (возможно пустая) последовательность символов из . Фиксируем некоторый конечный или счетный алфавит переменных

    Определение: Формула алгебры логики определяется следующим образом (индуктивное определение):

• Любая логическая переменная есть формула.
• Если - формула, то - формула (допустимы технические символы)
• Если и – формулы, то – тоже формулы (допустимы все логические связки).
• Других формул нет.

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

      Для сокращения записи формул обычно принимаются следующие соглашения:

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

    Принят  следующий порядок выполнения операций:

• Отрицание
• конъюнкция,
• дизъюнкция,
• импликация и эквивалентность в порядке их записи,

   Определение:  Формула называется тождественно истинной или тавтологией, если она реализует функцию «тождественная единица», и тождественно ложной, если 0.

   Упражнения

    Являются  ли формулы тождественно истинными:

    Тема 1.5. Законы и тождества Булевой алгебры.

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

    Возвращаясь к Шекспировскому примеру, и построив Таблицы истинности, мы легко покажем, что R=ØG.  

0	0	0	0	1	1	1	1	1
0	0	1	1	0	1	1	0	0
0	1	0	1	0	1	0	1	0
0	1	1	1	0	1	0	0	0
1	0	0	1	0	0	1	1	0
1	0	1	1	0	0	1	0	0
1	1	0	1	0	0	0	1	0
1	1	1	1	0	0	0	0	0

 

    Пример: Составим таблицу истинности следующей формулы:

      

0	0	0	1	1	1
0	0	1	1	1	1
0	1	0	1	0	0
0	1	1	1	1	1
1	0	0	0	1	0
1	0	1	0	1	0
1	1	0	1	0	0
1	1	1	1	1	1

 

    Пример: Составим таблицу истинности следующей формулы:

      

0	0	0	0	0	0	0
0	0	1	1	1	1	0
0	1	0	0	0	1	0
0	1	1	0	0	1	0
1	0	0	0	1	1	1
1	0	1	1	1	1	1
1	1	0	0	1	1	1
1	1	1	0	1	1	1

 

Как видите, построение таблиц истинности трудоемкий, но тривиальный процесс.

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

 – закон исключенного противоречия

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

Законы  идемпотентности:

Законы  отрицания

Закон навешивания двойного отрицания

Закон контрапозиции

    Эти тождества показывают, что отрицание  сложных выражений не такая уж тривиальная операция.

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

      – закон исключенного третьего, его часто объединяют с законом исключенного противоречия, от латинского (tertium non datur). Этот закон сформулирован Аристотелем. В «Метафизике» он писал: «Равным образом не может быть ничего посередине между двумя противоречащими друг другу суждениями, но об одном субъекте. Всякий отдельный предикат необходимо либо утверждать, либо отрицать».

    Действительно, нельзя одновременно высказать две  такие мысли об определенном объекте, например, числе, и обе мысли назвать  истинными: «Это число простое» и  «Это число непростое» и при этом иметь в виду одно и тоже число. Не нужно большого труда, чтобы определить, что только одна из них истинна. Например, «7 есть простое число» и «7 не есть простое число» - одно из этих высказываний обязательно ложно, третья же возможность обязательно исключается.

    Как и всякая формула, формальная запись упрощает, огрубляет закон. Из нее не видно, что закон исключенного третьего запрещает противоречащие высказывания только в том случае, если речь идет об одном и том же предмете, взятом в одно и то же время и в одном и том же отношении. Из истории логики известно, что критики формальной логики часто использовали этот закон с целью доказательства того, будто формальная логика вообще отрицает существование всяческих противоречий в природе и в мысли. Это неверно. Формальная логика запрещает, а точнее не рассматривает, только логически противоречивые мысли, т.е. противоречащие мысли по одному и тому же вопросу, в одно и тоже время.

    Именно  из закона исключенного третьего вытекает принятое в математической логике следующее  положение «Формула называется формально опровержимой, если доказуемо .

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

1. Когда одно из высказываний что-либо утверждает относительно единичного предмета или явления, а другое что-либо отрицает относительно этого же предмета или явления, взятого в одно и то же время и в одном и том же отношении. Например: «Нева впадает в Балтийское море», «Нева не впадает в Балтийское море». Оба эти высказывания не могут быть одновременно истинными или ложными, и невозможно никакое третье, среднее высказывание. Если кто-то выскажет, что «Нева впадает в Белое море», то такое высказывание не будет являться третьим, т.к. оно фактически совпадет со вторым.

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

Пусть имеется два таких высказывания «Все колхозы нашего района ввели правильные севообороты» и «Ни один колхоз нашего района не ввел правильного севооборота».

В этом случае из ложности одного высказывания, например 1, не следует истинность 2 высказывания. Может оказаться, что  истинно третье, промежуточное высказывание «Некоторые колхозы нашего района не ввел правильного севооборота». На эту тонкость применения закона указывал еще Аристотель. Такие высказывания он называл противоположными.

2. Когда одно из высказываний что-либо утверждает относительно всего класса предметов или явлений, а другое высказывание это же самое отрицает относительно части предметов или явлений этого же класса. Такими высказываниями будут, например, «Все рыбы дышат жабрами» и «Некоторые рыбы не дышат жабрами». Одно из таких высказываний обязательно истинно, а другое ложно, а третьего быть не может. Оба эти высказывания не могут быть истинными или ложными одновременно.
3. Закон исключенного третьего распространяется и на тот случай, если одно из высказываний что-либо отрицает относительно всего класса предметов, а другое высказывание это же самое утверждает относительно части предметов этого класса. Оба эти высказывания не могут быть истинными одновременно.