КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Булевы функции
Рассмотрим случай, когда элементами множества являются высказывания. Высказывание есть любое повествовательное предложение, о котором можно сказать истинно оно или ложно. Высказывание является основным понятием математической логики. Широкое применение, кроме самой математики, раздел «Математическая логика» получил при анализе и синтезе логических схем входа и выхода данных в компьютерах и других цифровых устройствах. Пример: «2x2=4» – истинное высказывание, «Все студенты МГУКи владеют двумя языками» -- ложное высказывание, «Да здравствует субботник» -- не высказывание. Обозначают высказывания прописными буквами латинского алфавита x, y,z; истинностные значения – цифрами 0 (ложно) и 1(истинно). Функции, аргументы и значения которых могут принимать только значения 0 и 1 называют булевыми функциями. Операциями над высказываниями являются: 1) отрицание -- такое высказывание, которое истинно, когда x – ложно и наоборот. -- отрицание (не x)
2) дизъюнкция (логическое сложение) – такое третье высказывание, которое ложно в единственном случае: когда x и y оба ложны; в остальных случаях оно истинно. -- дизъюнкция (x или y)
3) конъюнкция (логическое умножение) – такое третье высказывание, которое истинно лишь в одном случае, когда x и y оба истинны, в остальных случаях – ложно. -- конъюнкция (x и y)
4) импликация (логическое следствие) – такое третье высказывание, которое ложно в единственном случае, когда x—истинно, а y – ложно. В остальных случаях -- истинно.
-- импликация (если x, то y)
5) эквиваленция (логическое равенство) – такое третье высказывание, которое истинно, когда x и y принимают одинаковые истинностные значения, в остальных случаях – ложно. -- эквиваленция (тогда и только тогда)
Операции над высказываниями называют сентенциональными связями. С их помощью из элементарных высказываний можно получать сложные булевы функции (формулы). Порядок выполнения операций указывается скобками. Для упрощения записи принят ряд соглашений: n для отрицания скобки опускаются; n имеет приоритет перед ; n имеет приоритет . Любая булева функция определяется своей таблицей истинности. Пример: определим таблицу истинности булевой функции .
Две формулы алгебры высказываний равносильны, если они принимают одинаковые истинностные значения для всевозможных одинаковых истинностных значений в них входящих простых высказываний. Пример: -- формула для исключения импликаций Для установления равносильности формул, нужно составить таблицу истинности для левой и правой частей. Если истинностные значения совпадают, то формулы равносильны.
В алгебре высказываний имеют место следующие основные равносильности:
Замечание: заменив в формулах множества на высказывания, , получим, что законы алгебры множеств перейдут в законы алгебры высказываний; т.е. две алгебры отличаются лишь по форме входящих в них элементов. Алгебраически они неразличимы (изоморфны).
Если формула для любых значений истинности элементарных высказываний принимают только значения истинно(ложно), то она называется тождественно-истинной(тождественно-ложной) функцией. т.и.(т.л) – тавтологии – 1(0) Любая тавтология выражает собой некоторый логический закон. Пример: -- закон отделения
Число булевых функций от n переменных равно . Пример: если n=1, то ; Если n=2, то . Все они указаны в таблице:
У некоторых из этих функций есть специальные названия. -- тождественный нуль. -- конъюнкция. Часто знак не пишут () -- сложение по модулю 2. -- дизъюнкция. -- стрелка Пирса. -- эквивалентность. -- импликация. -- штрих Шеффера. -- тождественная единица. Часто при задании булевой функции ограничиваются указанием ее набора значений. Например, . Задачи.
a) ; b) ; c) ; d) . 2. Пусть значение высказывания a) истинно; b) ложно. Что можно сказать о значениях высказываний и ? 3. С помощью таблицы истинности доказать формулы: а) -- исключение импликации; b) -- исключение эквивалентности: . 4. С помощью таблицы истинности доказать законы: a) -- закон силлогизма; b) -- закон отделения; c) -- закон контрапозиции.
Дата добавления: 2014-11-29; Просмотров: 2074; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |