.RU

Лекция Математическая логика


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

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

Если любому значению аргумента ставится в соответствие значение 0 (1), то подобное отображение называется тождественным нулём (единицей).
Если любому значению аргумента ставится в соответствие он сам, то такая логическая функция называется тождественной.
Если любому значению аргумента ставится в соответствие противоположный элемент, то такая функция называется отрицанием или инверсией.
Для громоздких формул все действия, где операции применяются к промежуточным значениям формул, удобно представлять в виде таблицы, которую называют таблицей истинности.
^ Булевы функции двух переменных
1. Симметрические функции. Функция , которая равна 1, только если оба аргумента равны 1, называется конъюнкцией и обозначается как или .
Функция , значение которой равно 0, только если оба аргумента равны 0, называется дизъюнкцией.
Функция равная 1 только при совпадающих аргументах, называется эквиваленцией.
Функция , равная 0 только при совпадающих аргументах, называется суммой по модулю два. Термин сумма по модулю два и знак будем употреблять только тогда, когда речь идёт о булевых функциях, а термин строгая дизъюнкция и знак будем применять для высказываний, когда надо определить именно истинность, хотя это одно и то же.
Функция , равная 1, только если оба аргумента равны 0, называется стрелкой Пирса.
Функция , равная 0, только если оба аргумента равны 1, называется штрихом Шеффера.
2. Импликации. Функция , значение которой равно 0, только если первый аргумент равен 1, а второй 0, называется импликацией, или следуемостью.
3. Функции, явно зависящие от одной переменной.
Булева функция зависит от переменной существенно, если такой, что . В таком случае сама переменная называется существенной. Если не является существенной, т.е. выполняется равенство , то переменная называется фиктивной.
Логическую функцию можно задать аналитически, т.е. в виде формулы, или с помощью таблицы истинности, в левой части которой выписаны все возможные значения аргумента, а в правой – соответствующие им значения функции.
3.3. ^ Сложные высказывания
Операции над сложными высказываниями
В русском языке сложные предложения получают из двух других с помощью союзов и, а, если… то, либо, или, тогда и только тогда, когда и др. Такие и аналогичные им союзы называются логическими связками. Новые предложения появляются также с употреблением частицы не или слов неверно, что.
Утвердительные предложения, не содержащие (содержащие) логические связки, называют элементарными (составными) высказываниями. Очень часто в составных высказываниях простые предложения соединяются связкой или.
Предложение «Если программист не имеет специального образования, то он не будет конкурентоспособен на рынке труда» состоит из простых предложений, соединённых связками если… то и отрицаний не.
Если простое высказывание является истинным, то ему соответствует значение логической переменной 1. Если простое высказывание является ложным, то ему соответствует значение логической переменной 0.
Основными логическими операциями являются: отрицание (не), дизъюнкция (строгая (либо) и нестрогая (или)), конъюнкция (и), импликация (если… то), эквиваленция (тогда и только тогда).
Отрицанием, или инверсией, высказывания А называется высказывание , которое истинно, когда высказывание А ложно, и ложно, когда А истинно.
Дизъюнкцией (нестрогой или соединительной) высказываний А и В называется высказывание , которое истинно тогда и только тогда, когда истинно хотя бы одно из этих высказываний.
Конъюнкцией высказываний А и В называется высказывание АВ, которое истинно тогда и только тогда, когда истинны оба высказывания.
Строгой дизъюнкцией высказываний А и В называется высказывание АВ, которое истинно тогда и только тогда, когда истинно только одно из этих высказываний.
Импликацией высказываний А и В называется высказывание , которое ложно тогда и только тогда, когда из истины следует ложь.
Эквиваленцией высказываний А и В называется высказывание , которое истинно тогда и только тогда, когда либо истинны, либо ложны одновременно оба высказывания.
Пусть А: «Максимов – хороший программист», В: «Он побеждает на олимпиадах».
Нестрогая дизъюнкция : «Или Максимов хороший программист, или побеждает на олимпиадах». Строгая дизъюнкция АВ: «Либо Максимов хороший программист, либо побеждает на олимпиадах». Импликация : «Если Максимов хороший программист, то он побеждает на олимпиадах»; «Для того чтобы Максимов побеждал на олимпиадах, достаточно, чтобы он был хорошим программистом».
Эквиваленция : «Максимов хороший программист только когда он побеждает на олимпиадах».
Операция отрицания не всегда выражается в явном виде с помощью слов неверно или частицы не перед глаголом.
Добавление частицы не и слова неверно может не превратить высказывание А в отрицательное : «Максимов – хороший программист» и «Неверно, что Максимов – хороший программист», так как речь может идти о разных Максимовых.
Если высказывание имеет вид элементарного предложения без квантора общности, то не перед глаголом заменяет высказывание А на его отрицание .
Составим словарь перевода с русского языка на язык алгебры логики и включим в него таблицы истинности логических операций.
^ Словарь перевода на язык алгебры логики
Высказывание на русском языке
Соответствие в алгебре логики

Название
операций

Таблица
истинности

Не А;
неверно, что А;
А не имеет места



Отрицание,
инверсия



А или В;
или А, или В,
или оба вместе



Нестрогая
дизъюнкция (соединительная)



Либо А, либо В;
А или В, но не оба вместе



Строгая дизъюнкция (разъединительная)



А и В;
как А, так и В;
Не только А, но и В;
А вместе с В;
А, несмотря на В;
А, в то время как В


АВ

Конъюнкция





Если А, то В;
А, только если В;
А достаточно для В;
В необходимо для А;
А влечёт В;
В тогда, когда А;
Из А следует В



Импликация,
следование



А эквивалентно В;
А тогда и только тогда, когда В;
А, если и только если В;
А необходимо и достаточно для В


АВ

Тождественость, равносильность, эквиваленция





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


Здесь использовались следующие законы алгебры логики: a v b = b v a ab = ba – переместительный; - сочетательный закон;
- законы Де Моргана;
- правила операций с константой 1. - законы Порецкого;
- законы инверсии;

- снятие импликации.
Семантический способ представлен в таблице:

X

Y







0

0

1

0

1

0

1

1

0

1

1

0

0

0

1

1

1

1

1

1

Из таблицы видно, что теорема истинна при любом наборе значений Х и Y. Таким образом, доказана справедливость утверждения «Возможен дождь». Получение тождественной единицы подтверждает справедливость доказываемой теоремы.
^ Необходимое и достаточное условия импликации
Причина, посылка, т.е. высказывание, являющееся первым аргументом импликации, называется достаточным условием. В разговорной речи это то высказывание, которое находится между словами если… то, перед союзами поэтому, следовательно, значит или после союзов так как, потому что и т.д. «Для того чтобы ученик получил пятёрку», достаточно «правильно выполнить домашнее задание». «Ученик получил пятёрку», так как «правильно выполнил домашнее задание».
Следствие, заключение, т.е. высказывание, являющееся вторым аргументом импликации, называется необходимым условием. Оно стоит после союза то в предложениях с оборотами если… то, поскольку… то, так как… то, а также по другую от достаточного условия сторону по отношению к соединительным союзам.
Высказывание «углы вертикальные» является достаточным для утверждения «Углы равны». А равенство углов необходимо, чтобы утверждать, что речь идёт о вертикальных углах. Невыполнение необходимого условия влечёт за собой невыполнение достаточного условия, например, «Если углы не равны, то они не могут быть накрест лежащими».
Высказывание называется обратным высказыванием для высказывания , а высказывание - противоположным к импликации .
Равенство называется правилом контрапозиции.
Сформулируем высказывание, обратное противоположному: «Если стороны не равны (), то АВСD – не квадрат ()» или «Для того, чтобы АВСD был квадратом, необходимо чтобы его стороны были равны».
Примеры импликации:

Прямая и обратная теоремы не всегда имеют противоположный смысл.
Логические операции, в которых одновременно справедлива и прямая, и обратная импликация, называются эквиваленцией.
Высказывания с использованием таких операций можно формулировать с оборотом необходимо и достаточно: «Для того чтобы число делилось на 3, необходимо и достаточно, чтобы сумма цифр делилась на 3».
В некоторых случаях удобнее использовать слова тогда и только тогда.
В математике, когда аргументы каждой импликации сами являются сложными высказываниями, эквивалентность двух утверждений называется критерием.
Импликацией называется такая логическая операция, которая ложна тогда и только тогда, когда из истинного высказывания следует ложь.
Нестрогой дизъюнкцией двух высказываний называется такая логическая операция, которая ложна тогда и только тогда, когда оба высказывания ложны одновременно.
Если эквиваленцию определить по формуле , то приведённые выше определения будут содержать в себе круг: эквиваленция определяется через конъюнкцию и импликацию, а импликация и конъюнкция определяются словами тогда и только тогда, т.е. через эквиваленцию.
Выражение, в котором используется знак «= 1», является тождеством, оно истинно всегда, т.е. отличается от случая « 1» - эквиваленции. В общей алгебре знак «=» используется в уравнениях, и только корни уравнения, будучи подставлены в него, обратят его в тождество.


^ 3.4. Минимизация булевых функций
Разложение функций по переменным. Нормальные формы

Процесс замены громоздких булевых функций равносильными, но более простыми, путём использования законов алгебры логики, называется минимизацией булевых функций.
Минимизировать булевы функции надо, приводя их к нормальной форме.
Элементарной конъюнкцией (дизъюнкцией) называется выражение, состоящее из конечного числа переменных и их отрицаний, взятых в этом выражении не более одного раза и разделённых операциями конъюнкции (дизъюнкции):
, где или , например - элементарная конъюнкция; , где или , например - элементарная дизъюнкция;
Дизъюнктивной (конъюнктивной) нормальной формой называется дизъюнкция (конъюнкция) конечного числа элементарных конъюнкций (дизъюнкций).
Нормальная форма называется совершенной, если в каждой её элементарной дизъюнкции (конъюнкции) представлены все переменные, входящие в данную функцию (либо сами, либо с отрицанием). Например, для функции данное логическое выражение является совершенной ДНФ, сокращённо СДНФ. Любая булева функция, не являющаяся тождественным нулём или единицей, имеет только одну СДНФ с точностью до расположения переменных.
x1 x2 x3 F
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0
Задача. Пусть при п = 3 булева функция задана таблицей истинности. Составить СДНФ и СКНФ для данной функции.
Решение. Составим булеву функцию, объединив дизъюнкциейте элементарные конъюнкции, которые дают значение соответствующего булева выражения, равное единицt:
- СДНФ.
Чтобы построить СКНФ для функции F, надо взять дизъюнкцию элементарных конъюнкций, дающих значение, равное нулю, и взять отрицание от , так как .
. С помощью закона Де Моргана отрицание дизъюнкции превратим в конъюнкцию отрицаний и минимизируем выражение, сохраняя его вид, т.е. конъюнктивную форму.
.
Существование СДНФ позволяет провести процедуру, называемую разложением булевой функции по переменной . Разложение позволяет представить произвольную функцию в виде .


Логические схемы
Логическая схема имеет вид «чёрного ящика», в котором вход – набор булевых переменных, а выход – булева функция (рис.).
x1 x2 x3 F
0 0 0 1
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 0
Задача. По заданной таблице истинности найти логическую функцию.
Решение.

Минимизируем полученную формулу:





x1 x2 x3 F
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Задача. По заданной таблице истинности найти логическую схему.
Решение.


Минимизируем результат:

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





б)



kurs-po-viboru-dlya-9-klassa.html
kurs-po-viboru-dlya-uchashihsya-7-8-klassov-avtor-golub-natalya-vasilevna.html
kurs-po-viboru-fakultativ-uchebno-metodicheskij-kompleks-dlya-studentov-specialnosti-052300.html
kurs-po-viboru-iz-bloka-ds-v-doc-elena-leonidovna-grigoryan.html
kurs-po-viboru-obem-uchebnoj-nagruzki-30-chas-lekcii.html
kurs-po-viboru-po-uchebnoj-discipline-differencialnaya-psihofiziologiya-kredit-2.html
  • lektsiya.bystrickaya.ru/programma-po-kursu-.html
  • university.bystrickaya.ru/glava-tretya-chudovishnij-zver-i-pesni-lenivca-tri-bileta-do-edvencher.html
  • control.bystrickaya.ru/disciplina-truda.html
  • credit.bystrickaya.ru/oznachaet-chto-na-zapis-potrebuetsya-polnostyu-1-dvd-disk-etot-format-chitaetsya-na-vseh-dvd-pleerah.html
  • upbringing.bystrickaya.ru/kratkij-kurs-lekcij-po-medicinskoj-mikrobiologii-virusologii-i-immunologii-chast-pervaya-obshaya-mikrobiologiya-virusologiya-i-immunologiya.html
  • uchitel.bystrickaya.ru/r-majsuradze-proektirovanie-b-a-z-dannih-registrirovano-redakcionno-izdatelskim-sovetom-gtu-tbilisi-2008.html
  • exchangerate.bystrickaya.ru/fizlico-soinvestor-zaklyuchilo-dogovor-soinvestirovaniya-dlya-priobreteniya-zhilogo-doma-i-zemelnogo-uchastka-soinvestor-uplachivaet-investicionnij-vznos-v-poryadke.html
  • tasks.bystrickaya.ru/13-annotacii-primernih-programm-uchebnih-disciplin-variativnoj-chasti-professionalnogo-cikla-profilya.html
  • kontrolnaya.bystrickaya.ru/rabochaya-uchebnaya-programma-predmeta-menedzhment-po-specialnosti-himicheskaya-tehnologiya-organicheskih-veshestv.html
  • obrazovanie.bystrickaya.ru/pravitfunkcii-zarabotnoj-plati-voprosi-k-gosudarstvennomu-mezhdisciplinarnomu-ekzamenu.html
  • books.bystrickaya.ru/doklad-sedmoj-vnutriprirodnoe-vzaimodejstvie-62-vosmoj-doklad-sushnost-kormleniya-69.html
  • obrazovanie.bystrickaya.ru/programma-disciplini-psihologiya-kreativnosti-2-kurs-dlya-napravleniya-specialnosti-030300-62-psihologiya-podgotovki-bakalavra-avtor-programmi-yagolkovskij-s-r-k-p-n-.html
  • urok.bystrickaya.ru/pravila-obsledovaniya-nesushih-stroitelnih-konstrukcij-zdanij-i-sooruzhenij-sp-13-102-2003.html
  • college.bystrickaya.ru/325-svedeniya-o-nalichii-u-emitenta-licenzij-453256-rossiya-respublika-bashkortostan-g-salavat-molodogvardejcev.html
  • ekzamen.bystrickaya.ru/shema-mirovoj-istorii-filosofiya-i-teoriya-kulturi.html
  • occupation.bystrickaya.ru/na-vseh-etapah-razvitiya-chelovek-postoyanno-stremilsya-k-obespecheniyu-lichnoj-bezopasnosti-i-sohraneniyu-svoego-zdorovya-eto-stremlenie-bilo-motivaciej-mnogih-ego-d.html
  • institut.bystrickaya.ru/tema-3-chelovek-v-obshestvennom-kontekste-volkov-yu-g-mostovaya-i-v-v67-sociologiya-uchebnik-dlya-vuzov-pod-red.html
  • nauka.bystrickaya.ru/v-ya-gorfinkel-i-dr-pod-red-v-ya-gorfinkelya-m-prospekt-2010-637-s-bibliogr-s-625-629.html
  • lecture.bystrickaya.ru/aktualnie-voprosi-povisheniya-rentabelnosti-promishlennih-predpriyatij-i-obnovleniya-osnovnih-fondov-stranica-18.html
  • lecture.bystrickaya.ru/6-4-primeri-testovih-zadanij-uchebno-metodicheskij-kompleks-umk-uchebno-metodicheskij-kompleks-teoriya-i-metodika-vospitaniya.html
  • urok.bystrickaya.ru/press-dose-c-19-02-2011-po-21-02-2011.html
  • zadachi.bystrickaya.ru/mzhnarodna-ekonomka.html
  • tasks.bystrickaya.ru/32-mehanizmi-realizacii-koncepcii-socialno-ekonomicheskogo-razvitiya-ust-tarkskogo-rajona.html
  • kanikulyi.bystrickaya.ru/vsn-45-86-gosgrazhdanstroj.html
  • znanie.bystrickaya.ru/9-organizaciya-pitaniya-1-obshaya-harakteristika-obsheobrazovatelnogo-uchrezhdeniya-god-osnovaniya-shkoli-1980-god.html
  • prepodavatel.bystrickaya.ru/tipi-i-funkcii-gosudarstva.html
  • control.bystrickaya.ru/ekologiya-i-selskohozyajstvennaya-tehnika-konferenciya-sostoitsya-13-14-maya-2009-goda-v-konferenc-zale-gnu-szniimesh-rosselhozakademii-po-adresu-196625-sankt-peterburg-pavlovsk-po-tyarlevo-filtrovskoe-shosse-d-3.html
  • ucheba.bystrickaya.ru/predislovie-stranica-7.html
  • literatura.bystrickaya.ru/slovar-lozhnih-druzej-perevodchika4-kursovaya-rabota-tema-leksicheskie-trudnosti-v-processe-perevoda-zaimstvovanij.html
  • credit.bystrickaya.ru/plan-konspekt-uroka-tema-zhizn-i-tvorchestvo-gaziza-almuhametova-cel-poznakomit-obuchayushihsya-s-zhiznyu-i-tvorchestvom-bashkirskogo-kompozitora-gaziza-almuhametova.html
  • lektsiya.bystrickaya.ru/pravila-pozharnoj-bezopasnosti-dlya-uchrezhdenij-zdravoohraneniya-ppbo-07-91-stranica-12.html
  • school.bystrickaya.ru/dejstvuyushij-mehanizm-ischisleniya-i-vzimaniya-akcizov-i-ego-sovershenstvovanie.html
  • shpargalka.bystrickaya.ru/uroven-organizacii-bernard-verber-enciklopediya-otnositelnogo-i-absolyutnogo-znaniya.html
  • gramota.bystrickaya.ru/zakoni-str-304-342-stranica-2.html
  • thesis.bystrickaya.ru/pressa-gosduma-rf-monitoring-smi-20-maya-2008-g.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.