Дискретная математика Тема: Математическая логика Преподаватель Белгородцева Н.А.

Цель лекции – познакомить студентов: 1)с суждениями как формой мышления; 2)с булевыми функциями; 3)со сложными высказываниями; 4)с минимизацией булевых функций ; 5)с полином Жегалкина.

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

Характеристика суждения по признаку истинности-ложности называется семантической. Пример. «0>5» - ложное высказывание; «12>5» - истинное высказывание; «х>5» не является высказыванием. Истину можно обозначать символом 1, а ложь – символом 0. Формализацией высказываний называют операцию замены высказывания естественного языка формулой математического языка, включающего высказывательные переменные и символы тех логических операций, которые соответствуют структуре самого высказывания.

3.2. Булевы функции Отображение,где называется булевой функцией n переменных. Две булевы функции f и g, зависящие от n переменных, называются равными (эквивалентными), если для любого справедливо соотношение. Формула представляет соответствующую логическую функцию. Формулы могут состоять из самих аргументов (переменных) или включать в себя другие функции.

Булевы функции одной переменой Если любому значению аргумента ставится в соответствие значение 0 (1), то подобное отображение называется тождественным нулём (единицей). Если любому значению аргумента ставится в соответствие он сам, то такая логическая функция называется тождественной. Если любому значению аргумента ставится в соответствие противоположный элемент, то такая функция называется отрицанием или инверсией.

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

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

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

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

3.3. Сложные высказывания Операции над сложными высказываниями Союзы и, а, если… то, либо, или, тогда и только тогда, когда и аналогичные им союзы называются логическими связками. С их помощью, а также с употреблением частицы не или слов неверно, что создаются новые предложения. Утвердительные предложения, не содержащие (содержащие) логические связки, называют элементарными (составными) высказываниями.

Пример. Предложение «Если программист не имеет специального образования, то он не будет конкурентоспособен на рынке труда» состоит из простых предложений, соединённых связками если… то и отрицаний не. Если простое высказывание является истинным, то ему соответствует значение логической переменной 1. Если простое высказывание является ложным, то ему соответствует значение логической переменной 0.

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

Дизъюнкцией (нестрогой или соединительной) высказываний А и В называется высказывание, которое истинно тогда и только тогда, когда истинно хотя бы одно из этих высказываний. Конъюнкцией высказываний А и В называется высказывание АВ, которое истинно тогда и только тогда, когда истинны оба высказывания. Строгой дизъюнкцией высказываний А и В называется высказывание А В, которое истинно тогда и только тогда, когда истинно только одно из этих высказываний.

Импликацией высказываний А и В называется высказывание, которое ложно тогда и только тогда, когда из истины следует ложь. Эквиваленцией высказываний А и В называется высказывание, которое истинно тогда и только тогда, когда либо истинны, либо ложны одновременно оба высказывания. Пусть А: «Максимов – хороший программист», В: «Он побеждает на олимпиадах» - простые высказывания. Рассмотрим примеры сложных высказываний.

Нестрогая дизъюнкция : «Максимов хороший программист или он побеждает на олимпиадах». Строгая дизъюнкция А В:«Либо Максимов хороший программист, либо он побеждает на олимпиадах». Импликация :«Если Максимов хороший программист, то он побеждает на олимпиадах». Эквиваленция : «Максимов хороший программист тогда и только тогда, когда он побеждает на олимпиадах».

Операция отрицания не всегда выражается в явном виде с помощью слов неверно или частицы не перед глаголом. Пример. А – «В магазине много товаров»; - «В магазине мало товаров». Добавление частицы не и слова неверно может не превратить высказывание А в отрицательное : Пример. А - «Максимов – хороший программист» и - «Неверно, что Максимов – хороший программист». Высказывания не обязательно противоположные, так как речь может идти о разных Максимовых.

Рассмотрим таблицы истинности логических операций. Отрицание,инверсия ( ) Не А; неверно, что А; А не имеет места. Нестрогая дизъюнкция (соединительная) ( ) А или В; или А, или В, или оба вместе

Строгая дизъюнкция (разъединительная) ( ) Либо А, либо В; А или В, но не оба вместе Конъюнкция (А В,, ) А и В; как А, так и В; не только А, но и В; А вместе с В;А, несмотря на В; А, в то время как В

Импликация, следование( ) Если А, то В; А, только если В; А достаточно для В; В необходимо для А; А влечёт В; В тогда, когда А; из А следует В Тождественость, равносиль- ность, эквиваленция (,, ) А эквивалентно В; А тогда и только тогда, когда В; А, если и только если В; А необходимо и достаточно для В

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

- переместительный закон - сочетательный закон - закон де Моргана - закон Порецкого - правила операций с 1 - закон инверсии - снятие импликации

Задача. Поможем синоптикам определить прогноз погоды. Известно, что если атмосферное давление понижается, то возможен дождь. В настоящее время атмосферное давление понижается. Возможен ли дождь? Решение. Пусть Х – атмосферное давление понижается; Y – возможен дождь. Высказывание: «Если давление понижается, то возможен дождь» имеет вид:. Тогда «Если давление понижается, то возможен дождь. Давление понижается» можно записать в виде конъюнкции. Сформулируем теорему:

Докажем истинность вывода, используя оба способа. Синтактический способ.

Семантический способ представлен в таблице: Из таблицы видно, что теорема истинна при любом наборе значений Х и Y. Таким образом, доказана справедливость утверждения «Возможен дождь». Получение тождественной единицы с помощью законов подтверждает справедливость доказываемой теоремы

Необходимое и достаточное условия импликации Причина, посылка, т.е. высказывание, являющееся первым аргументом импликации, называется достаточным условием. В разговорной речи это то высказывание, которое находится между словами если… то, перед союзами поэтому, следовательно, значит или после союзов так как, потому что и т.д. «Для того чтобы ученик получил пятёрку», достаточно «правильно выполнить домашнее задание». «Ученик получил пятёрку», так как «правильно выполнил домашнее задание».

Следствие, заключение, т.е. высказывание, являющееся вторым аргументом импликации, называется необходимым условием. Оно стоит после союза то в предложениях с оборотами если… то, поскольку… то, так как… то, а также по другую от достаточного условия сторону по отношению к соединительным союзам. ABABAB

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

Высказывание называется обратным высказыванием для высказывания, а высказывание - противоположным к импликации. Равенство называется правилом контрапозиции. Пусть А – «АВСD - квадрат»; В – «стороны равны». :«Для того, чтобы АВСD был квадратом, необходимо чтобы его стороны были равны». :«Если стороны не равны, то АВСD – не квадрат»

Примеры импликации: для того чтобы диагонали четырёхугольника были равны, достаточно, чтобы четырёхугольник был квадратом; равенство диагоналей четырёхугольника – необходимое условие для существования прямоугольника; для того чтобы четырёхугольник АВСD был квадратом, достаточно, чтобы его диагонали были равны, перпендикулярны и делились точкой пересечения пополам (каждое из этих трёх условий является необходимым для квадрата).

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

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

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

Элементарной конъюнкцией (дизъюнкцией) называется выражение, состоящее из конечного числа переменных и их отрицаний, взятых в этом выражении не более одного раза и разделённых операциями конъюнкции (дизъюнкции):, где или, например - элементарная конъюнкция;, где или,например - элементарная дизъюнкция;

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

Любая булева функция, не являющаяся тождественным нулём или единицей, имеет только одну СДНФ с точностью до расположения переменных. Задача. Пусть при n= 3 булева функция задана таблицей истинности. Составить СДНФ и СКНФ для данной функции. х1х1 х2х2 х3х3 F

Решение. СДНФ: по строкам, в которых булева функция принимает значение 1, составляем элементарные конъюнкции, которые затем объединяем дизъюнкциями. В конъюнкцию входит сама переменная, если её значение в данной строке равно 1, и отрицание этой переменной, если её значение равно 0. х1х1 х2х2 х3х3 F

Решение. СКНФ: по строкам, в которых булева функция принимает значение 0, составляем элементарные дизъюнкции, которые затем объединяем конъюнкциями. В дизъюнкцию входит сама переменная, если её значение в данной строке равно 0, и отрицание этой переменной, если её значение равно 1. х1х1 х2х2 х3х3 F

Существование СДНФ позволяет провести процедуру, называемую разложением булевой функции по переменной. Разложение позволяет представить произвольную функцию в виде p и q – функции, не зависящие от. Пример. Функция разложена по переменной.

Задача. По заданной таблице истинности найти логическую функцию. Решение. Составим СДНФ: Минимизируем полученную функцию, предварительно разложив её по переменной : Здесь был применён закон алгебры логики – закон склеивания:. х1х1 х2х2 х3х3 F

х1х1 Логические схемы Логическая схема имеет вид «чёрного ящика», в котором вход – набор булевых переменных, а выход – булева функция х3х3 F х2х2

Задача. По заданной таблице истинности построить логическую схему. Решение. Минимизируем результат: Для минимизации применили разложение по, законы склеивания,переместительный, распределительный и Порецкого. х1х1 х2х2 х3х3 F

х2х2 Построим два варианта логических схем по булеву выражению: а) б) х3х3 х2х2 х1х1 ИЛИ И б х3х3 х1х1 И И

Карты Карно Карты Карно являются одним из наиболее удобных способов минимизации. Это специальные таблицы, дающие возможность упростить процесс поиска минимальной формы булева выражения с помощью графического представления для количества переменных n6. Они имеют вид прямоугольника, разделённого на 2 n клеток, в каждой из которых – двоичный n-мерный набор значений функции F из таблицы истинности. Отрицанию переменной соответствует значение 0, самой переменной – значение 1.

Логическая функция F на карте представлена совокупностью клеток, заполненных единицами или нулями, если известны её значения при всём наборе аргументов, т.е. известна таблица истинности или СДНФ. Для построения минимальной ДНФ производится «склеивание» единиц. Склеиваются только соседние клетки, которые отличаются значением одной переменной. Процесс сводится к объединению в группы единичных клеток карт Карно. При этом общие переменные сохраняются, а различные опускаются.

Алгоритм «склеивания» 1.Привести булеву функцию к ДНФ. 2.Нанести единицы на карту Карно. 3.Объединить соседние единицы контурами, охватывающими 2 т клеток, где т=0, 1, 2, 3. При этом может оказаться, что единица попадает одновременно в два контура. Контуры следует делать по возможности крупнее. 4.Провести упрощения, т.е. в каждом контуре оставить только общие переменные, объединённые конъюнкцией. 5.Объединить конъюнкции дизъюнкциями.

Пример 1. Как видно, общее во всех конъюнкциях – В, следовательно, Пример

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

Пример 3. Пример

Пример 5. Пример

2.5. Полином Жегалкина В СДНФ булевой функции только одна из элементарных конъюнкций равна 1. Это даёт основание представить любую булеву функцию с помощью операции сложения по модулю два. Заменив в СДНФ на и используя распределительный закон для конъюнкции относительно сложения по модулю два, имеем. Тогда, учитывая, что, а, булеву функцию можно представить в виде суммы по модулю два конъюнкций.

Пример. Представим в виде полинома Жегалкина функцию, заданную в виде СДНФ: