Элементы математической логики Основные определения алгебры логики. Элементарные булевы функции. Законы и тождества алгебры ло. Лекция 8. Лекция 8 Элементы математической логики

• Название: Лекция 8 Элементы математической логики
• Анкор: Элементы математической логики Основные определения алгебры логики. Элементарные булевы функции. Законы и тождества алгебры ло
• Дата: 04.04.2022
• Размер: 489.41 Kb.
• Имя файла: Лекция 8.pptx
• Тип: Лекция; #442708

Лекция 8

Элементы математической логики

Основные определения алгебры логики. Элементарные булевы функции. Законы и тождества алгебры логики. Понятие о нечеткой логике

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

Разделы и подходы к мат.логике

Высказывания

Высказывание - повествовательное предложение (утвер­ждение, суждение), о котором имеет смысл говорить, что оно истинно или ложно.
Примеры высказываний: "Дважды два - четыре", "Мы живем в XXI веке", "Доллар - американская валюта", "Алеша - брат Олега", "Операции объединения, пересечения и дополнения являют­ся булевыми операциями над множествами", "Человек смер­тен", "От перестановки мест слагаемых сумма не меняет­ся", "Сегодня понедельник", "Если идет дождь, вам следует взять зонт.
Любое высказывание имеет истинностное значение (Истина или Ложь)

История развитая математической логики

Логика как наука сформировалась в 4 в. до н.э. Ее создал гречес­кий ученый Аристотель. Слово «логика» происходит от греческого "логос", что с одной стороны означает "слово" или "изложение", а с другой мышление.
".В 17 в. немецкий ученый Лейбниц задумал создать новую науку, ко­торая была бы «искусством исчисления истины». В этой логике, по мысли Лейбница, каждому высказыванию соответствовал бы символ, а рассуждения имели бы вид вычислений. Эта идея Лейбница, не встретив понимания современников, не получила распространения и развития и осталась гениальной догадкой.
Только в середине 19 в. ирландский математик Джордж Буль воплотил идею Лейбница. В 1854 году им была написана работа "Исследование законов мышления" (Investigation the laws of thought), которая заложила основы алгебры логики.
Алгебра логики Буля явилась зародышем новой науки – математической логики.


В конце 19 в. созданная Георгом Кантором теория множеств предста­влялась надежным фундаментом для всей математики, в том числе и математической логики, по крайней, мере, для исчисления высказываний (алгебры Буля), т.к. оказалось, что алгебра Кантора (теория множеств) изоморфна алгебре Буля.
В начале 20 в. (1910 г.) русский ученый Эренфест П.С. указал на возможность применения аппарата булевой алгебры в телефонной связи для описания переключательных цепей. В 1938-1940 г. почти одновременно появились работы советского ученого Шестакова В. И., американского ученого Шеннона и японских ученых Накасимы и Хакадзавы о применении математической логики в цифровой технике. Пер­вая монография, посвященная использованию математической логики при проектировании цифровой аппаратуры, была опубликована в СССР советским ученым Гавриловым М.А. в 1950 г.


Чрезвычайно важна роль математической логики в развитии современной микропроцессорной техники: она исполь­зуется в проектировании аппаратных средств ЭВМ, в разработке всех языков программирования и в конструировании дискретных устройств автоматики.
Большой вклад в развитие математической логики сделали ученые разных стран: профессор Казанского Университета Порецкий П.С., де-Морган, Пирс, Тьюринг, Колмогоров А.Н., Гейдель К. и др

Логика высказываний. Основные понятия и определения

Истинность высказывания обозначается единицей, а ложность – нулем. Простое высказывание не зависит от значений других высказываний. Значение истинности сложного высказывания зависит от истинности других высказываний, составляющих его.
Предложение "х2 = 4" не является высказыванием, для того, чтобы имело смысл говорить об его истинности или ложности, необходимы допол­нительные сведения, в частности, какое число обозначено буквой "х", т.к. она может не обозначать конкретного числа, - а быть переменной, т.е. представлять элементы некоторого множества, например (-2. О, 2, 4).
Каждому значению переменной соответствует либо истинное, либо ложное высказывание; например высказывания (-2)2 = 4, 22 =4 истинны, остальные ложны.
Предложение, которое содержит хотя бы одну переменную и становится высказыванием при подстановке вместо всех переменных их значений, называют высказывательной или пропозициональной (ПФ) формой.

Предикаты и кванторы

Говорят, что определена некоторая функция, если, 1) зада­но некоторое множество, называемое областью определения функции или областью отправления, 2) задано некоторое множество, назы­ваемое областью значений (прибытия) функции и, 3) указанно определенное правило, с помощью которого каждому элементу, взятому из области определения, становится в соответствие некоторый элемент из области значений.
Произвольный элемент взятый из области определения функции назы­вается аргументом и обозначается “х”. Правило соответствия обозначае­тся F, т.о. запись у=F(х)
означает, что х - аргумент, у - функция, F - правило соответствия.
Функция, область определения которой задана множеством М, а все значения которой, принадлежат множеству {1, 0} называется предикатом.
Пример 1: Если переменная “х” в высказывательной форме "Река х впадает в Каспийское море" принимает значение из множества М названий всевозможных рек, то эта форма задает предикат.


Выражение "для всякого х" называется кванторам общности по переменной х (вместо х может быть любая другая переменная) и запи­сывается  х (Ф (х)).
Выражение, "существует х, такое что..." называется квантором существования по переменной х и обозначается  х (Ф(х)), что означает существует значение "х" такое, что Ф(х) при этом значении - истинное высказывание.
Переход от формы Ф(х) к высказыванию  х (Ф(х)) или  х (Ф(х)) называется операцией квантификацией формы Ф(х).
Будем называть переменную "х" в Ф(х) после применения к ней операции квантификации связанной переменной. В отличие от связанных переменных, переменные в первоначальном смысле слова называются свободными переменными.


 х (х^2≥0)
 х (х^2≥4)
   х (P (x) & Q(x, y))
  y(P (y) ѵ Q(x, y))

Булевы функции, булевы константы

Булевыми функциями (или функциями алгебры логики или истинностными функциями) называются функции, значения которых равны 0 или 1 и аргументы которых принимают только два значения 0 и 1.
Булевы функции могут быть заданы специальными таблицами истин­ности или аналитически в виде специальных высказывательных форм, называемых иногда булевыми формами.
Выражения, содержащие одну или несколько переменных (аргумен­тов), соединенных знаками логических операций, называются логическим формами. Высказывания, не содержащие ни одной переменной, называются константами. В логике, в отличие от арифметики, только две константы 0 - false и 1- true.


Булевыми функциями называются предикаты, все аргументы которых определены на множестве {0, 1}, интерпретируемые как {ложь, ис­тина}.
Понятие булевой функции является частным случаем понятия предиката. Отличие состоит лишь в том, что у булевой функции четко фиксирована как область определения {0, 1}, так и область значений функции {0, 1}, в то время как у предиката четко фиксирована только одна область значений {0, 1}, в то время как область определения задана произвольным множеством.
В свою очередь понятие предиката является частным случаем понятия функции, отличие состоит в том, что у предиката четко фиксирована область значений {0, 1}, а у функции это может быть вся числовая ось.

Основные логические связки

Отрицание (логическая связь "не")
Записывается Р=Ā или в виде P= ¬A (Читается "Р есть не А"). Отрицанием называется сложное логическое высказывание Р, которое истинно, если А ложно и наоборот.

Конъюнкция

Р = А Ʌ В; Р = А & В. (Читается Р есть А и В).
Конъюнкция - сложное логическое высказывание, которое истинно только в случае истинности всех составляющих высказываний, в противном случае ложно.

	A Ʌ 0 = 0; A Ʌ Ā = 0; A Ʌ 1 = A.

Дизъюнкция

Р = А v В (читается Р есть А или В). Дизъюнкция - это сложное логическое высказывание, которое ложно только в случае ложности всех составляющих высказываний, в противном случае истинно (vel - или (лат.)).

	A v 1 = 1; A v Ā = 1

Импликация

Импликацией высказываний А и В называется высказывание, обозначенное символами А → В, которое ложно тогда и только тогда, когда А истинно, а В ложно.
Читается А влечет В либо "А имплицирует В", импликация - это логическая операция, соответствующая союзу "если... то".
Запись А → В означает то же, что и высказывание : "если А то В", "из А вытекает В" "А есть достаточное условие для В", для того чтобы А необходимо, чтобы В ", "В есть необходимое условие для А", " для того чтобы В, достаточно чтобы А".
Первый член А называется антецедентом (от лат. antecedens - предшествующий), а второй член В - консеквентом (от лат. consequens - последующий).

	1. Импликация с ложным антецедентом всегда истинна. 2. Импликация с истинным консеквентом всегда истинна. 3. Импликация ложна тогда и только тогда, когда ее антецендент истинный, а консеквент ложный

Эквиваленция или равнозначность

Эквиваленцией высказываний А и В называется высказывание, обозначаемое символом А ↔ В (или ,, ), которое истинно тогда и только тогда, когда значения истинности высказываний А и В совпадают.
Логическая операция, называемая эквивалентностью, соответствует союзу "тогда и только тогда, когда" и читается "А эквивалентно В", "Для того, чтобы А необходимо и достаточно, чтобы В".
Когда мы говорим "А только тогда, когда В" то имеем в виду, что оба предложения А и В одновременно истинны, либо одновременно ложны. Например, говоря: "Я поеду в Астану тогда и только тогда, когда ты поедешь в Караганду", мы утверждаем, что-либо произойдет и то и другое, либо ни того, ни другого.
Можно доказать используя таблицу истинности, что для любых высказываний А и В высказывание (А ↔ В) = 1 тогда и только тогда, когда (А → В) = 1 и (В → А) = 1.


Для любых высказываний А и В высказывание
(А ↔ В) = 1 тогда и только тогда, когда (А → В) = 1 и (В → А) = 1.
Это утверждение используется при доказательстве теорем вида А ↔В. Одним из способов доказательства истинности высказывания А → В является доказательство истинности высказывания А → В (необходимость) и истинности высказывания В → А (достаточность).
Высказывания А и В называются равносильными, если (А ↔ В) = 1

Равносильность

Говорят, что формулы F1 и F2 равносильны, если их эквиваленция F1↔F2 - тавтология (тождественно истинное высказывание).
Запись F1  F2 читается : "формула F1 равносильна формуле F2"
А ↔ В  (А → В)  (В → А)
Равносильность есть отношение между формулами (также как равенст­во отношение между числами, параллельность - отношение между прямыми).
Отношение равносильности обладает следующими свойствами:
а) рефлективности F  F
б) симметричности: если F1 F2 то F2 F1
в) транзитивности: если F1F2 и F2 F3, то F1 F3

В математической логике для записи более сложных высказываний используются следующие логические операции над простыми высказываниями:  НЕ & И  ИЛИ → влечет ↔ совпадает.

Алгебра логики

Функцию типа f: Mn→M будем называть n - арной операцией на множестве М; n называется арностью операции f.
Алгеброй А называется совокупность < M,S> множества М с заданными на нём операциями S={f11, f12,..., f1k, f21, f22, ..., f2l, ..., fn1, ..., fnm}
A=, где М - называется основным или несущим множеством (или просто носителем) алгебры А.
Вектор арностей алгебры называется её типом, совокупность операций S - сигнатурой алгебры.
Первый индекс у идентификатора операции указывает её местность.
Для идентификации единого целого, содержащего объекты, которые имеют различное математическое строение, например множество операций в нём, было предложено использовать термин совокупность и обозначать его угловыми скобками.


Особую роль будет играть двухэлементное множество В ={0,1} ={True, False} ={Истина, Ложь}
В контексте, содержащем одновременно двоичные и арифметические величины и функции, эта интерпретация фиксируется явно: например, в языках программирования (Паскаль и др.) вводится специальный тип переменной - логическая переменная, значения которой обозначаются true и false.
Алгебра, образованная множеством В вместе с всеми возможными операциями на нём, называется алгеброй логики.
Функцией алгебры логики (или логической функцией) от n переменных называется n - арная операция на B.
Множество всех логических функций обозначается P2,
множество всех логических функций от n переменных – P2(n).
Алгебра, образованная к - элементным множеством вместе со всеми операциями на нём, называется алгеброй к - значной логики, а n - арные операции на к - элементном множестве называются к - значными логическими функциями n переменных;
множество всех к - значных функций обозначается Pk.
Множество всех к - значных логических функций от n переменных обозначается Pk(n).


Всякая логическая функция n переменных может быть задана таблицей истинности, в левой части которой перечислены все 2n наборов переменных (т.е. двоичных векторов длины n), а в правой части - значения функций на этих наборах. Наборы, на которых функция f = 1, часто называют единичными наборами функции f, а множество единичных наборов - единичным множеством f. Соответственно наборы, на которых f = 0, называют нулевыми наборами f.
В таблице истинности наборы расположены в определённом порядке - лексикографическом, который совпадает с порядком возрастания наборов, рассматриваемых как двоичные числа. Этим упорядочением будем пользоваться и в дальнейшем. (01, 10, 11 или 001, 010, 011, 100, 101, 111 и т.д.)
При любом фиксированном упорядочении наборов логическая функция n-переменных полностью определяется вектор - столбцом значений функции, т.е. 2n. Поэтому мощность множества |P2(n)| т.е. число различных логических функций n переменных равно числу различных двоичных векторов длины 2n, т.е.
N =


Переменная xi в функции f(x1, x2, ..., x(i-1), xi, x(i+1), ..., xn) называется несущественной (или фиктивной), если f(x1, x2, ..., x(i-1), 0, x(i+1), ..., xn) = f(x1, x2, ..., x(i-1), 1, x(i+1), ..., xn) при любых значениях остальных переменных, если изменение значения xi в любом наборе x1,..., xn не меняет значения функции.
В этом случае функция f(x1,..., xn) по существу зависит от n-1 переменной, т.е. представляет собой функцию g(x1, x2, ..., x(i-1), x(i+1), ..., xn-1) от n-1 переменной. Говорят, что функция g получена из функции f удалением фиктивной переменной xi, а функция f получена из g введением фиктивной переменной, причём эти функции по определению считаются равными. Например, запись f(x1, x2, x3)= g(x1, x2) означает, что при любых значения x1 и x2 f = g независимо от значения переменной x3.
Смысл удаления фиктивных переменных при минимализации функции очевиден, поскольку они не влияют на значения функции и являются с этой точки зрения лишними. Однако иногда бывает полезно вводить фиктивные переменные. Благодаря такому введению всякую функцию от n переменных можно сделать функцией большего числа переменных.
В частности, только это доказанное равенство |P2(n)|= справедливо при условии, что P2(n) содержит все возможные функции n переменных, в том числе и функции с фиктивными переменными.

Основные логические функции

Формулы алгебры логики состоят из букв, знаков логических опе­раций и скобок. Буквы обозначают логические (двоичные) переменные, которые принимают только два значения -"ложь" и "истина". Знаки операций обозначают логические операции (логические связки).
Каждая формула задает логическую функцию - функцию от логических переменных, ко­торая сама может принимать только два логических значе­ния.


Алгебра логики - алгебра, образованная множеством В ={0, 1} вместе со всеми возможными операциями на нем.
Функцией алгебры логики (или логической функцией) f от п переменных f (х1, х2 ..., хn) называется п-арная логичес­кая операция на В, т.е. f: Вn —> В.
Множество всех логичес­ких функций (логических операций) обозначается Р2, мно­жество всех логических операций п переменных - Р2 (п).
Любую логическую функцию f (х1, х2 ..., хn) можно задать таблицей истинности, в левой части которой выписаны все возможные наборы значений ее аргументов х1, х2 ..., хn,, а пра­вая часть представляет собой столбец значений функций, соответствующих этим наборам.


Набор значений перемен­ных, на котором функция принимает значение f=1, называ­ется единичным набором функции f; множество всех еди­ничных наборов - единичным множеством функции f.
Набор значений, на котором f= 0, называется нулевым набором функции f,
а множество нулевых наборов - нулевым множеством.
Число всех возможных различающихся наборов значений п переменных логической функции f (х1, х2 ..., хn) равно 2n (рав­но числу всех возможных двоичных векторов длины п).
Число всех различных функций п переменных равно числу возмож­ных расстановок нулей и единиц в столбце с 2n строками, т.е. |Р2 (п)|= 22n.
Особую роль в алгебре логики играют логические функ­ции одной и двух переменных - унарные и бинарные логи­ческие операции, так как очевидным образом интерпретиру­ются естественными логическими связками "не", "и", "или" и т.д., широко используемыми при описании систем, явле­ний, формализации рассуждений и пр.

Пример

Пример
f0 и f3, - константы 0 и 1 соответственно. Значения этих функций не зависят от переменной х, в таких случаях говорят, что переменная х является несущественной (фиктивной) для этих функций;
f1(х) =х (повторение переменной), f2(х) =⌐х

х	f0	f1	f2	f3
0	0	0	1	1
1	0	1	0	1

Множество всех логических функций двух переменных Р2(2) - бинарных логических операций

Изображение функций в виде логической схемы

f7(х1, х2)= х1↓х2 –стрелка Пирса, читается как «ни x1 ни х2». Функция f9 принимает значение 1 только в том случае, если х1 = 0 и х2 = 0, и значение 0 в противном случае.
f14(х1, х2)= х1|х2 называется функцией Шеффера. Читается «неверно, что х1 и x2» . Функция f14 принимает значение 0 только в том случае, если х1 = 1 или x2 = 1, и значение 1 в противном случае.
F6(х1, х2)= х1 х2 называется функцией сложения по модулю 2. Читается «х1 неравнозначно х2». Функция принимает значение 1 только в том случае, если переменные х1 и x2 имеют различные значения, и значение 0 в противном случае.


Таким образом, формула наряду с таблицей служит спо­собом задания и вычисления функции. В общем случае фор­мула описывает логическую функцию как суперпозицию других более простых функций.
Эквивалентными, или равносильными, называются фор­мулы, представляющие одну и ту же функцию (эквивалент­ность формул в алгебре логики обозначается знаком = ).
Стандартный метод установления эквива­лентности двух формул:
1) по каждой формуле восстанавливается таблица истин­ности;
2) полученные таблицы сравниваются по каждому набо­ру значений переменных, (стандартный метод требует 2 • 2n вычислений).

Полнота системы булевых функций

Система булевых функций называется функционально полной, если она позволяет представить любую булеву функцию. Так, рассмотренные ранее функции от двух переменных f2, f4, f2, f6- f9, f11, f13 – f14 могут быть представлены с помощью трех функций: отрицания, дизъюнкции и конъюнкции.
Полным набором служит также единственная функция – функция Шеффера x1/x2. В этом легко убедиться, выразив через нее три выше упомянутых функции полного набора:
Полный набор представляет собой также и функция Пирса (f8).
Логические элементы, соответствующие функционально полным наборам булевых функций, образуют так называемый базис и позволяют построить любую сколь угодно сложную логическую схему.

Постулаты алгебры логики

Существуют такие 0 и 1, что =1 и =0. Необходимо отме­тить, что цифры 0 и 1 не выражают здесь количественных соотношений и являются не числами, а символами и, следовательно, алгебра логики является не алгеброй чисел, а алгеброй состояний.
2. Переменная может принимать лишь одно из двух возможных значений
x = 0, если, x  1
x = 1 если, x 0
3. Действия с константами
0  0 = 0 1  1 = 1
1  1 = 1 0  0 = 0
1  0 = 0 0  1 = 1
0  1 = 0 1  0 = 1

Законы алгебры логики. Теоремы одной переменной

1. Закон тождества Х=Х. Необходимо, чтобы мысль, заключенная в высказывании не менялась в течение всего рассуждения.
2. Закон нулевого множества:
0  а = 0
0  а = а
0  а  b  …  x = 0
3. Закон универсального множества:
1  а = а
1  а = 1
1  а  b  …  z = 1
4. Закон тавтологии, повторения (идемпотентности):
а  а …  а = а а  а  …  а = а
Истина, повторенная несколько раз, все равно, остается только истиной.
5. Закон двойной инверсии (инволютивности): . Отрицание отрицания равносильно утверждению.⌐ (⌐а)=а
6. Законы дополнительности:
а) закон логического противоречия . Произведение любой пере­менной и ее отрицания всегда ложно (утверждение "речка дви­жется и не движется" всегда ложно);
б) закон исключенного третьего . Сумма любой переменной и ее отрицания всегда истинна: "Студент или сдаст экзамен или не сдаст". "Паду ли я стрелой пронзенный, иль мимо пролетит она".

Теоремы для двух и трех переменных

7. Коммутативные (переместительные) законы:
а  b = b  а а  b = b  а
От перемены мест слагаемых сумма не меняется.
8. Ассоциативные (сочетательные) законы:
а  (b  c) = (a  b)  c ассоциативность конъюнкции.
а  (b  c) = (а  b)  c ассоциативность дизъюнкции.
Для записи умножения или сложения скобки можно опустить.
9. Дистрибутивные (распределительные) законы:
а) умножение относительно сложения а  (b  c) = а  b  а  c
а (b + с) = аb + ас (в обычной алгебре)
б) сложение относительно умножения
a  b  c = (a  b)  (a  c)
a+bc  (a+b) (a+c) (в обычной алгебре)

Тавтологии. Равносильные формулы

ПФ, значения которых для любого набора переменных есть 1 (соответственно 0) будем называть тождественно истинными формулами, или тавтологиями (тождественно-ложными ПФ или противоречием).
Тавтологии играют в логике особо важную роль как формулы, отражающие логическую структуру предложений, истинных в силу одной только этой структуры. Для доказательства того, что ПФ является тавтологией доста­точно построить таблицу истинности для этой ПФ. Обозначим | = А, что А тавтология.

Перечислим некоторые основные тавтологии или законы логики.

Две ПФ и назовем равносильными, если для любых наборов они принимают одинаковые значения.
Это обозначается АВ и читается "А равносильно В" (равно­сильность рефлексивна, симметрична и транзитивна).
Теорема 8.1. А  В тогда и только тогда, когда | = А ↔ В.
Убедимся, что теорема верна, если докажем необходимость: если АВ, то | = А  В; достаточность: если | = А  В, то А  В. Справедливость этих утверждений вытекает непосредственно из оп­ределений.
Принцип двойственности: Если две формулы, (не содержащие знаков →, и ↔) равносильны, то двойственные ил формулы равносильны.
Две формулы называются двойственными, если каждую из них можно получить из другой заменой ,  , 1, 0 соответственно на  , , 0 и 1 (X  0 = Х  1).
Обратные и противоположные теоремы. Для каждого предложения, формализованного импликацией А → В, можно составить три таких пред­ложения В → А, и . ,
Предложение В → А называется об­ратным данному, предложения противоположным данному и обратно противоположным. Для всякой теоремы вида "если А, то В" можно сформулировать обратное ей предложение "если В, то А".