Учебное пособие по математической логике для студентов заочного отделения




НазваниеУчебное пособие по математической логике для студентов заочного отделения
страница3/5
Дата публикации28.08.2013
Размер0.96 Mb.
ТипУчебное пособие
skachate.ru > Математика > Учебное пособие
1   2   3   4   5

^ Полиномы Жегалкина.

Существует и другой, отличный от СДНФ и СКНФ стандартный способ представления логических функций. Любая логическая функция (в том числе тождественно ложная и тождественно истинная функции) может быть представлена в виде полинома Жегалкина:

,

где коэффициенты имеют значения 0 или 1. Для примера снова рассмотрим функцию



Поскольку и конъюнкция любых двух конъюнктов, входящих в равна нулю, знаки дизъюнкции в выражении функции можно заменить на :



Кроме того, воспользуемся тем, что :



Поскольку , окончательно получаем:

.

Заметим, что .

^ Полные системы функций и базисы.

Как уже говорилось, логические функции можно определять с помощью суперпозиций:

подставив в функцию вместо функцию , а вместо функцию , получим, вообще говоря, новую функцию . Такой набор логических функций , что с помощью суперпозиций функций из этого набора можно получить любую логическую функцию, называется полной системой функций. Очевидно, такие системы существуют, например, система всех логических функций. Однако поскольку любую логическую функцию можно представить либо в виде СДНФ, либо в виде СКНФ, либо и в том, и в другом виде, полной системой функций является уже набор из трех функций: отрицание, конъюнкция и дизъюнкция. Поскольку любую функцию можно представить в виде полинома Жегалкина, полной системой функций является набор из сложения по модулю 2, конъюнкции и единицы. Но конъюнкцию можно представить в виде суперпозиции отрицания и дизъюнкции: , а дизъюнкцию – в виде суперпозиции отрицания и конъюнкции: . Поэтому наборы из отрицания и конъюнкции и отрицания и дизъюнкции – тоже полные системы функций. Но если из любого из этих наборов исключить хотя бы одну функцию, этот набор перестанет быть полной системой функций – эти полные системы функций являются минимальными, то есть базисами. Базисами являются еще два набора, каждый из которых состоит только из одной функции. Это базис Пирса, включающий лишь стрелку Пирса ( ) и базис Шеффера, включающий только штрих Шеффера ( ).

На множестве логических функций выделяют функционально замкнутые классы функций, (замкнутые относительно суперпозиций, классы Поста): если функции принадлежат к одному классу Поста, то и любая их суперпозиция принадлежит этому классу Поста. Этих классов пять. Рассмотрим эти классы.

1) – класс функций, сохраняющих ноль, то есть если , то . Очевидно, к этому классу принадлежат тождественный нуль, конъюнкция, дизъюнкция, вычитание и сложение по модулю 2, но не принадлежат тождественная единица, отрицание, импликация, стрелка Пирса, штрих Шеффера и эквиваленция.

2) – класс функций, сохраняющих единицу, то есть если , то . Очевидно, к этому классу принадлежат тождественная единица, конъюнкция, дизъюнкция, импликация и эквиваленция, но не принадлежат тождественный нуль, отрицание, вычитание, стрелка Пирса, штрих Шеффера и сложение по модулю 2.

3) – класс самодвойственных функций, то есть если , то . Очевидно, к этому классу принадлежат функции и отрицание и не принадлежат все остальные функции.

4) – класс линейных функций, то есть если , то , где – коэффициенты, каждый из которых равен либо 0, либо 1. Очевидно, к этому классу принадлежат тождественная единица, тождественный нуль, , и не принадлежат все остальные функции.

5) – класс монотонных функций. Для определения этого класса надо ввести отношение частичного порядка на множестве наборов значений переменных. Для двух наборов выполнено отношение предшествования , если . Функция , если . Очевидно, к этому классу принадлежат тождественные нуль и единица, функция конъюнкция и дизъюнкция, и не принадлежат все остальные функции.

Нетрудно доказать функциональную замкнутость каждого из этих классов (доказательство предоставляется читателю).

Теорема Поста. Для того, чтобы набор функций был полной системой функций, необходимо и достаточно, чтобы он не содержался целиком ни в одном из классов Поста.

Секвенции.

Отношение равносильности, введенное на множестве формул алгебры логики, является отношением эквивалентности. Это отношение делит множество всех возможных высказываний на классы эквивалентности: высказывания, относящиеся к одному классу, утверждают, в сущности, одно и то же, хотя, возможно, другими словами. Но в рассуждениях часто устанавливается, что из одного высказывания логически следует другое, причем из второго высказывания первое может и не следовать. Например, из высказывания ‘‘Число делится на 6’' следует высказывание ‘‘Число делится на 3’', но не наоборот. Отношение логического следования является отношением частичного порядка. Пусть – набор формул, – формула. Выражение называется секвенцией. Секвенция называется истинной, если на всех наборах значений переменных, на которых истинна каждая из формул набора , истинна и формула . Если набор пуст, и секвенция имеет вид , она называется тавтологией. Такая секвенция истинна в том и только том случае, если тождественно истинная формула. Наоборот, выражение указывает на то, что набор формул противоречив.

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

Свойства знака следования |=. Пусть – список формул, – формулы.

1. при (элементарные следствия).

2. Если , то (добавление допущений).

3. Если при и , то (доказательство с помощью лемм).

Для доказательства истинности секвенций можно использовать табличный метод. Докажем, например, истинность секвенции . При этом удобнее будет обозначать отрицание знаком . Кроме того, значения переменных будем записывать под самими переменными, а значения функций под знаками функций. Строчки, соответствующие тем наборам переменных, при которых каждая из формул набора в левой части принимает значение 1, будем подчеркивать:


0 0 0 | 1 | 1 0 0 |0 |0 0 0 0 1 1 0 |1| 0 0 0

0 0 0 | 1 | 1 0 0 |0 |0 0 1 0 1 1 0 |1| 0 0 1

0 0 1 | 1 | 0 1 1 |1 |0 0 0 0 1 0 1 |1| 0 0 0

0 0 1 | 1 | 0 1 1 |1 |0 0 1 0 1 0 1 |1| 0 0 1

1 0 0 | 1 | 1 0 0 |0 |1 0 0 1 1 1 0 |1| 1 0 0

1 0 0 | 1 | 1 0 0 |1 |1 1 1 1 1 1 0 |1| 1 0 1

1 1 1 | 0 | 0 1 1 |1 |1 0 0 1 0 0 1 |0| 1 0 0

1 1 1 | 0 | 0 1 1 |1 |1 1 1 1 0 0 1 |1| 1 1 1
Видно, что в пересечениях подчеркнутых строк с выделенными столбцами везде стоят единицы. Следовательно, секвенция доказана.

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

когда Если и ,

то Если и , то





(для любого )~

Правила преобразования списков допущений.

Пусть списки формул, формулы и . Следующие списки допущений равносильны:

1) и (правило перестановки),

2) и (правило сокращения),

3) и (правила объединения и расщепления).

Пример. Доказательство тавтологии с помощью свойств символа следования, правил введения и удаления знаков логических операций и правил преобразования списков допущений.

1) – свойство 1,

2) – свойство 2, удаление ,

3) – введение , 1, 2,

4) – введение , 3,

5) – введение , 4,

6) – свойство 1,

7) – свойство 2, удаление ,

8) – введение , 6, 7,

9) – свойство 3, удаление ,

10) – введение , 9,

11) – введение , 10,

12) – свойство 3, введение ~, 5, 11.

^ Метод резолюций.

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

Рассмотрим метод резолюций на примере доказательства следующей тавтологии:



Тавтология будет доказана, если доказать тождественную ложность противоположного высказывания:



Сначала мы преобразуем формулу в левой части, чтобы получить ее КНФ:



При этих преобразованиях использовались законы де Моргана, снятие двойного отрицания и равносильность . В результате получилась КНФ формулы в левой части. Но если при каком-то наборе значений переменных истинна формула , то при этом же наборе значений переменных каждый из элементарных дизъюнктов является истинным, то есть истинность этой формулы эквивалентна истинности каждой формулы из набора (списка допущений):

1) , 2) , 3) , 4) , 5) (формулы нумеруем для удобства ссылок).

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

.

Добавляем формулу в список допущений:

1) , 2) , 3) , 4) , 5) , 6) .

Обозреваем этот список, и в нем не обнаруживаем очевидных допущений. Снова используем резолюцию первого типа и получаем, что из формул и следует формула . Записываем:

.

Добавляем и эту формулу в список допущений:

1) , 2) , 3) , 4) , 5) , 6) , 7) .

Теперь очевидно, что список допущений противоречив – противоречат друг другу допущения 5) и 7). Тавтология доказана.
^ 3. Исчисления высказываний
Как уже говорилось, алгебра высказываний основывается на определениях логических операций с помощью таблиц истинности. Тем самым эта логическая теория имеет частный, не вполне формальный характер. В то же время в современной математике (и физике) идеальным считается построение теории как формальной теории на основе аксиоматического метода, для чего необходимы:

1) явная формулировка аксиом теории;

2) явная формулировка правил вывода, используемых для последовательного построения теории;

3) использование искусственно построенного формального языка для изложения всех утверждений теории.

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

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

Множество символов (‘‘абстрактных букв’’), используемых в теории, называется ее алфавитом. Алфавит исчисления высказываний состоит из объединения четырех множеств: , где , , , . Других символов алфавит исчисления высказываний не содержит. Буквы множества называются пропозициональными переменными. Символ называется символом следования. Конечный ряд написанных друг за другом букв называется словом в этом алфавите.

Формулой исчисления высказываний называется слово алфавита, удовлетворяющее следующим условиям:

  1. пропозициональная переменная является формулой, которая называется элементарной, или атомарной.

  2. если и – формулы, то , , и – тоже формулы.

Никаких других формул нет, поэтому слово – не формула, так как не имеет внешних скобок, однако принято внешние скобки опускать, и тогда – тоже формула.

Различных исчислений высказываний существует много. Все они делятся на два типа: исчисления гильбертовского типа (по имени крупнейшего немецкого математика конца девятнадцатого – начала двадцатого века Д. Гильберта) и исчисления генценовского типа (по имени немецкого математика и логика первой половины двадцатого века Г. Генцена). В исчислениях гильбертовского типа много аксиом и мало (основных) правил вывода, а в исчислениях генценовского типа – наоборот.

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

  1. A1. ;

A2. ;

II. A3.

A4.

A5.

III A6.

A7.

A8.

IV A9.

A10.

A11.

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

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

Основное правило вывода в ИВ всего одно: правило простого заключения: если в выводе есть формулы и , то в вывод можно добавить формулу . Аналогичное правило известно с древности, его латинское название ‘‘modus ponens’’ (сокращенно MP).

В качестве примера рассмотрим доказательство теоремы .

1) ;

2)

3)

4) ;

5)

Формула 1) представляет собой схему A2, в которой вместо подставлено , вместо – формула , вместо – формула . Формула 2) представляет собой схему A1 с той же подстановкой. Формула 3) получена из формул 1) и 2) по правилу MP. Формула 4) получена из схемы 1 подстановкой формулы вместо и . Формула 5) получена по правилу MP из формул 4) и 3).

Формальный вывод секвенции .

1) – допущение,

2) – допущение,

3) – A1,

4) – MP 2, 3,

5) – A2,

6) – MP 1, 5,

7) – MP 4, 6.

Построение выводов бывает достаточно сложным. Его часто облегчает следующая

Теорема о дедукции. Если , то . В частности, если , то .

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

Основные правила вывода:
1) (введение ),

2) (удаление ),

3) (введение ),

4) (удаление разбор случаев),

5) (введение ),

6) (удаление ),

7) (удаление , или доказательство от противного),

8) (выведение противоречия),

9) (перестановка посылок)

10) (утончение, или правило лишней посылки).

Пример. Вывод в ИС секвенции .

1) – аксиома,

2) – аксиома,

3) – удаление , 1, 2,

4) – аксиома,

5) – удаление , 3, 4,

6) – аксиома,

7) – удаление , 5, 6.
1   2   3   4   5

Похожие:

Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие по ботанике для студентов 3 курса заочного отделения...
Учебное пособие предназначено для самостоятельной работы студентов 3 курса заочного отделения фармацевтического факультета. Пособие...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие для самостоятельной работы студентов заочного отделения...
Учебное пособие предназначено для для самостоятельной работы студентов заочного отделения неязыков специальностей вузов, ранее изучавших...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие для самостоятельной работы студентов заочного отделения...
Учебное пособие предназначено для для самостоятельной работы студентов заочного отделения неязыков специальностей вузов, ранее изучавших...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие по органической химии для самостоятельной работы...
Учебное пособие предназначено для самостоятельной работы студентов II курса заочного отделения фармацевтического факультета при выполнении...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие по фармацевтической химии для студентов 4 курса заочного...
Авторы учебного пособия для студентов 4 курса заочного отделения фармацевтического факультета «Общие и частные методы анализа лекарственных...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие содержит характеристику основных разделов фармацевтической...
В пособии приведена рабочая программа по фармацевтической химии для студентов заочного отделения, даны рекомендации по её освоению...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие по органической химии для самостоятельной работы студентов
Учебное пособие предназначено для самостоятельной работы студентов II курса заочного отделения фармацевтического факультета при выполнении...
Учебное пособие по математической логике для студентов заочного отделения iconРекомендации о разработке методических указаний и контрольных заданий...
Разработчик: методист заочного учебного отделения высшего профессионального образования С. С. Кудрявцева
Учебное пособие по математической логике для студентов заочного отделения iconСамостоятельная работа, часов
Смолова Л. М. Химия. Рабочая программа, методические указания, элементы теории, вопросы для самопроверки и контрольные задания для...
Учебное пособие по математической логике для студентов заочного отделения iconКонтрольная работа №2 по английскому языку для студентов заочного...
Данное пособие можно взять в библиотеке Политехнического колледжа или получить в электронном виде. Также необходимо изучить материалы...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
контакты
skachate.ru
Главная страница