Модуль 3. Алгебра логики (1,5 кредита) Комплексная цель и задачи изучения модуля

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

В результате освоения Модуля 3 студент должен быть готов продемонстрировать следующие компетенции и уровень подготовки:

1. умение применять на практике законы и тождества алгебры логики, доказывать справедливость тождеств алгебры логики;

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

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

Самостоятельная работа предусматривает проработку лекций (1,2 часа в неделю), тестирование, а также изучение литературы, формулировку цели работы, объекта и задач исследования, методов, источников и средств библиографического поиска, использованных для достижения поставленной цели.

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

Глава 12. Элементы алгебры логики

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

Д. Локк

Алгебра логики, основные логические функции, основные логические операции, основные логические тождества и законы

ЦЕЛИ

Освоив эту главу, учащиеся должны знать и уметь:

• определять основные логические функции;

• строить таблицы истинности логических функций и операций;

• доказывать истинность логических тождеств;

12.1. Логические функции

Логика - это искусство рассуждений. Создатель логики – Аристотель. Наука о законах и формах мышления, так определил логику Аристотель. Лейбниц предложил ввести в логику математическую символику и использовать ее для общих логических построений. Эту идею реализовал в прошлом столетии Джордж Буль и заложил основы математической (символьной) логики.

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

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

Все люди смертны.

Сократ – человек.

Следовательно, Сократ смертен.

В XIX веке Пирс сформулировал абдуктивную логику. В ее основу он положил три основных принципа (Непейвода Н.Н.):

- индукция – получение общего закона по множеству частных случаев;

- дедукция – получение из общего утверждения другого общего либо частного;

- абдукция – получение нового частного случая из множества частных случаев.

Основная задача математической логики (МЛ): заменить рассуждения вычислениями». Основа математической логики была заложена в трудах де Моргана, Буля, Пирса, Кантора, Геделя, Маркова, Клини, Ляпунова и многих других ученых. Марков говорил: «Математическая логика – логика по предмету, математика по методу». Язык математической логики, ставший символическим языком современной математики, возник, когда неудобство математического языка для нужд математики было окончательно осознано. Следовательно, математическая логика – наука, изучающая саму математику математическими средствами.

Математическая логика изучает формальную структуру рассуждений математическими средствами. Язык математической логики – исторически первый, точно определенный формальный язык.

Существует двузначная и многозначная логика. Двузначная логика имеет дело с объектами, которые принимают одно из двух возможных значений (0, 1). Объекты, содержащие и принимающие значения из конечного множества, содержащего больше двух элементов, называют многозначными, они обрабатываются аппаратом многозначной логики или сводятся к двузначным объектам.

Высказывание – утверждение об объектах имеющих однозначный, точно определенный смысл. Например, В году 365 дней; 2  2 = 5; 3  3 = 9 и т.д. некоторые высказывания являются истинными, некоторые ложными. Выделяют, безусловно истинные высказывания (3  3 = 9) и безусловно ложные (2  2 = 5). Высказывания, говорящие о множестве утверждений называются общими. Атомарными элементарными высказываниями считают такие, которые сообщают единичный факт. Сложные образуются из атомарных применением трех операций:

- Логические связки применяются к высказываниям и, в результате, получается новое высказывание. Например, это «A и B»; « не только A, но и B и C»;

- Модальности применяются к высказываниям и изменяют наше отношение к ним. Например, «говорят, что A > B»; «по словам ученых…»;

- Кванторные конструкции применяются к совокупности однородных (отличающихся лишь значениями некоторых параметров) высказываний либо выражений и дают единое высказывание либо выражение, не зависящее от указанных параметров. Например, «Большинство…»; «Все…»; «Для любого…».

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

Определение 1. Единственными логическими значениями являются истина и ложь, обозначаемые (1 или 0, И или Л).

Определение 2. Логическое значение сложного утверждения зависит лишь от логических значений его компонентов, а не от его смысла.

Простейшие из выражений, обозначающих предметы, т.е. их конкретные имена, называются константами. Выражение, обозначающее предмет, называется термом.

Для образования высказывания из предметов их соединяют отношением. Например, a = b – двуместное отношение, сопоставляющее двум числам a и b высказывание a = b, в частности 1 = 1 – истинное высказывание, а 1 = 9 – ложное.

В математической логике часто используется запись P(t₁, t₂, …, t_n), чтобы обозначить высказывание, образованное применением n-местного отношения P к предметам t₁, t₂, …, t_n. Символ P, изображающий отношение называется предикатом, а t₁, t₂, …, t_n – термы.

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

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

Особенность ЛФ в том, что они принимают значения в конечных множествах. Область значений ЛФ - это конечная совокупность чисел, символов, любых объектов. ЛФ могут зависеть от одной, двух и любого числа переменных (аргументов). Аргументы могут принимать значения из элементов как конечных, так и бесконечных множеств.

Логическая функция Y = f(x₁, x₂, ..., x_n) - это отображение множества наборов (n-мерных векторов, кортежей вида (x₁, ..., x_n)) на множество ее значений N = {₁, ..., l₂}. Если аргументы принимают значения из того же множества что и сама функция, то ее называют однородной.

Объекты с двумя возможными состояниями характеризуются булевыми переменными, которые принимают лишь два различных значения. Отношения между булевыми переменными представляются булевыми функциями y = f(x), но y и x принимают свои значения из двухэлементного множества {0, 1}. Множество всех БФ вместе с операциями отрицания, конъюнкции и дизъюнкции образует Булеву Алгебру (БА). Основные в БА три функции: отрицание, дизъюнкция и конъюнкция. Более сложные формулы получаются замещением входящих в них переменных другими логическими формулами, которые обычно заключаются в скобки, например.

Логическое отрицание (операция НЕ, инверсия) - это операция, результат которой является истинным тогда, когда исходное высказывание ложно, и наоборот.

Обозначается как . Таблица истинности этой операции будет иметь следующий вид:

x
0	1
1	0

Логическое сложение (операция ИЛИ, дизъюнкция) - это операция, которая истинна, когда истинно хотя бы одно из составляющих ее высказываний, и ложна - в случае, если оба высказывания ложны. Обозначается как x  y. Данная операция является многоместной. Таблицу истинности этой операции можем записать так:

х	y	x  y
0	0	0
1	0	1
0	1	1
1	1	1

Логическое умножение (операция И, конъюнкция) - это операция, которая истинна тогда и только тогда, когда истинны оба составляющих ее высказывания, и ложна во всех остальных случаях. Записывается как: x & y, или x  y или x y. Данная операция является многоместной. Таблица истинности этой операции будет выглядеть следующим образом:

x	y	x & y
0	0	0
1	0	0
0	1	0
1	1	1

Импликация - это операция, которая ложна тогда, когда исходное высказывание истинно, а конечное - ложно, и истинна - во всех остальных случаях. Записывается в виде x  y. Таблица истинности этой операции будет иметь следующий вид:

x	y	x  y
0	0	1
1	0	0
0	1	1
1	1	1

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

x	y	x  y
0	0	1
1	0	0
0	1	0
1	1	1

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

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

Связки , , , , - называются связками исчисления высказываний или пропорциональными связками.

Принцип бритвы Оккама: «Не умножай сущностей без необходимости».

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

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

Квантор  сочетается со связкой , а квантор  - со связкой . Например, утверждение «Некоторые хорошие (Х(x)) студенты (С(x)) становятся учеными (У(x))» можно записать в виде

x(Х(x)  С(x)  У(x)).

Например, утверждение: «Все сторожевые (СС(x)) собаки (С(x)) – злые (Зл(x))»:

x(С(x)  СС(x))  Зл(x).

Перевод утверждения «для всякого целого числа есть большее» можно записать:

x(x  Z  y(y  Z  y > x)),

где Z – множество целых чисел.

Основной закон равенства: Если A – произвольная формула языка формальной теории, то

x, y (x = y  (A(x)  A(y)))

Другими словами, свойства равных объектов эквивалентны.

Определение Лейбница: Два предмета равны, если они обладают одинаковыми свойствами.

Тождественно истинные формулы в математической логике называются тавтологии. Если формула A – тавтология, то она обозначается |= A.

В математической индукции имеется базис – утверждение, что свойство выполнимо для самого маленького из рассматриваемых чисел, и шаг – обоснование перехода от числа n к числу n + 1. На языке математической логики метод математической индукции запишется

A(0)  n (A(n)  A(n + 1))  n A(n).

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

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Пример 12.1. Определить значение следующего составного высказывания:

x  (   z  y  )   y

при условии, что х = 1; y = 0; z = 0.

Решение. Поскольку рассматриваемое высказывание состоит из двух частей, соединенных между собой операцией дизъюнкции, то, возможно, окажется достаточно определить значение только одной из составляющих его частей (в случае, если окажется, что эта составляющая истинна). Рассмотрим ту часть, которая содержит меньше переменных. Для этого подставим заданные значения переменных и получим выражение 0  0. Очевидно, что данное выражение ложно. В таком случае продолжим рассмотрение второй части исходного выражения. Здесь у нас имеет место операция конъюнкции. Поскольку

переменная х истинна, рассмотрим выражение в скобках:

  z  y  .

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

0  1  0  0  1.

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

Пример 12.2. Для составного логического высказывания, заданного в примере 1, определить такой набор значений логических переменных x, y, z, при котором значение составного высказывания было бы ложно.

Решение: Поскольку в исходном высказывании имеется операция дизъюнкции, то для того, чтобы это высказывание было ложным, необходимо, чтобы одновременно были ложны высказывания: x  (   z  y  ) и  y. Рассмотрим эти высказывания по отдельности, причем поскольку второе высказывание содержит меньше переменных, начнем именно с него. Очевидно, что для того, чтобы было ложно высказывание  y, необходимо, чтобы либо , либо y, либо обе переменные одновременно были ложны. Таким образом, с учетом инверсии переменной x получили три возможных набора значений переменных x и y:

(x = 1, y = 1; x = 1, y = 0; x = 0, y = 0).

Теперь рассмотрим вторую составляющую:

x  (   z  y  ).

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

Возьмем первый набор: x = 1, y = 1. Поскольку х истинно, то значение высказывания в скобках должно быть ложным. Подставив значения x и y в высказывание в скобках, получим:

0  0  z  1  .

Это выражение может быть ложно в двух случаях. Во-первых, если переменная равна нулю, в таком случае вне зависимости от результата импликации данное выражение будет ложно. А во-вторых, оно будет ложно, если будет ложным результат импликации. Как известно, операция импликации ложна только в случае, если левая половина импликации истинна, а правая - ложна. Из данного высказывания видно, что результат импликации будет ложным в случае, если z = 1.

Таким образом, мы получили два набора значений переменных, при котором исходное высказывание ложно: х = 1, y = 1, z = 1; х = 1, y = 1, z = 0.

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

1) x = 0, y = 0, z = 0;

2) x = 0, y = 0, z = 1.

Ответ. Полученный результат можно записать в виде таблицы истинности (см. табл. 12.1) логической функции Y:

Y = x  (   z  y  )   y.

Таблица 12.1

x	y	z	Y
0	0	0	0
1	0	0	1
0	1	0	1
1	1	0	0
0	0	1	0
1	0	1	1
0	1	1	1
1	1	1	0