Основные определения и операции над высказываниями

Тема 4 БУЛЕВЫ ФУНКЦИИ

Общие сведения об алгебраических системах

Алгебраическая система – это множество с определенными на нем операциями и отношениями. Алгебраическая система – это объект A, где - непустое множество, - семейство алгебраических операций, а - семейство отношений, заданных на множестве. Множество называется носителем алгебраической системы, а его элементы – элементами системы. Алгебраическая система называется конечной, если множество конечно.

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

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

Пусть A и B - две алгебраические системы одного и того же типа. Отображение, называется гомомофизмом системы A в систему B, если выполняются следующие условия:

1. и

2. для всех и.

Если - гомоморфизм, то его обозначают A ® B.

Гомоморфизм A ® B являющийся инъекцией, называется мономорфизмом. Гомоморфизм A ® B, являющийся сюръекцией, называется эпиморфизмом и при этом система B называется гомоморфным образом системы A. Гомоморфизм A ® A называется эндоморфизмом. Сюръективный мономорфизм A ® B, для которого гомоморфизм, называется изоморфизмом и обозначается A «B. Изоморфизм A «A называется автоморфизмом системы A.

Понятие изоморфизма – одно из важнейших понятий в современной математике. При изоморфизме сохраняются действие всех основных операций и отношений. Это позволяет переносить изучение свойств с одной системы на другую.

Логика (в переводе с древнегреческого) означает слово, выражающее мысль. В современном понимании логика - это наука о способах мышления. Математическая логика служит для создания алгоритмов логического вывода.

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

Исходным понятием математической логики является «высказывание». Высказывание - это повествовательное предложение, которое истинно или ложно. Оно не может быть истинным и ложным одновременно. Высказывания обозначаются большими буквами латинского алфавита А, В,…. Любое высказывание рассматривается как переменная величина, так называемая высказывательная или пропозициональная переменная, принимающая значения 1 (истина) или0 (ложь).

Высказываниями являются, например, следующие предложения. «3 есть простое число». «Киев – столица Узбекистана». Первое из них истинно, второе – ложно.

Высказывание называется элементарным (простым), если любую его часть нельзя рассматривать как отдельное высказывание. В процессе рассуждений из одних высказываний формируются другие более сложные высказывания. Они получаются из исходных высказываний добавлением частицы «НЕ», а также соединением высказываний с помощью связок «И», «ИЛИ», «ЕСЛИ..,ТО» ТОГДА И ТОЛЬКО ТОГДА, КОГДА» и других. Эти связки соответствуют логическим операциям над пропозициональными переменными.

Далее указывается приоритет (очерёдность выполнения) основных логических операций и даются их определения.

1. Отрицанием высказывания X называется высказывание, которое истинно тогда и только тогда, когда Х ложно. В разговорной речи высказывание соответствует составлению из высказывания Х нового высказывания «не Х».

2. Конъюнкцией двух высказываний Х и Y называется высказывание Х Ù Y, которое истинно тогда и только тогда, когда истинны оба высказывания. Конъюнкция иначе называется логическим умножением, а Х и Y – сомножителями. В разговорной речи конъюнкция соответствует соединительному союзу «и».

3. Дизъюнкцией двух высказываний Х и Y называется высказывание Х Ú Y, которое ложно тогда и только тогда, когда Х и Y ложны. Дизъюнкция иначе называется логическим сложением, а Х и Y – слагаемыми. В разговорной речи дизъюнкция соответствует соединительному союзу «или».

4. Импликацией двух высказываний Х и Y называется высказывание Х → Y, которое ложно тогда и только тогда, когда Х – истинно, а Y – ложно. В разговорной речи импликация высказываний соответствует высказыванию вида: «если Х, то Y».

5. Эквиваленцией двух высказываний Х и Y называется высказывание Х ↔ Y, которое истинно тогда и только тогда, когда истинностные значения высказываний Х и Y совпадают. В разговорной речи эквиваленция двух высказываний соответствует выражению «Х тогда и только тогда, когда Y».

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

ПФ от n переменных можно рассматривать как функцию, которая произвольному набору из n нулей и единиц ставит в соответствие 0 или 1. Такая функция называется двоичной, булевой или переключательной функцией.

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

Например, таблица истинности основных логических операций имеет вид

X	Y

Дата добавления: 2014-01-11