![]() |
Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Свойства логических операцийСтр 1 из 3Следующая ⇒
Свойства логических операций Логические операции Простейшим и наиболее широкоприменяемым примером такойалгебраической системы являетсямножество B, состоящее всего из двухэлементов: B = { Ложь, Истина }. Как правило, в математическихвыражениях Ложь отождествляется слогическим нулём, а Истина — слогической единицей, а операцииотрицания (НЕ), конъюнкции (И) идизъюнкции (ИЛИ) определяются впривычном нам понимании. Легкопоказать, что на данном множестве Bможно задать четыре унарные ишестнадцать бинарных отношений, представленных в таблице справа, однако все они могут быть полученычерез суперпозицию трёх выбранныхопераций. Опираясь на этот математическийинструментарий, логика высказыванийизучает высказывания и предикаты. Также вводятся дополнительныеоперации, такие как эквивалентность Логика высказываний послужилаосновным математическиминструментом при созданиикомпьютеров. Она легко преобразуетсяв битовую логику: истинностьвысказывания обозначается однимбитом (0 — ЛОЖЬ, 1 — ИСТИНА); тогдаоперация Впоследствии булева алгебра была обобщена от логики высказываний путём введения характерных длялогики высказываний аксиом. Это позволило рассматривать, например, логику кубитов, тройственную логику(когда есть три варианта истинности высказывания: «истина», «ложь» и «не определено») и др. -- Свойства логических операций 1. Коммутативность: x 2. Идемпотентность: x 3. Ассоциативность: (x 4. Дистрибутивность конъюнкций и дизъюнкции относительно дизъюнкции, конъюнкции и суммы по модулю двасоответственно: · x · x · x 5. Законы де Мо́ ргана: · · 6. Законы поглощения: · x · x 7. Другие (1): · x · x · x · x · 8. Другие (2): · · · 9. Другие (3) (Дополнение законов де Мо́ ргана): · · Булевы функции. Представление булевой функции логической формулой. Геометрическое представление Bn можно рассматривать как единичный n-мерный куб. Каждый набор из нулей и единиц длины n задает вершину этого куба. На рис. 3.1 представлены единичные кубы Bn при n=3, 4.
При этом существует естественное взаимно однозначное соответствие между подмножествами вершин n-мерных единичных кубов и булевыми функциями от n переменных: подмножеству Например, верхней грани куба B3 (ее вершины выделены на рисунке) соответствует функция f: f(0, 0, 1)=f(0, 1, 1)=f(1, 0, 1)=f(1, 1, 1) =1 и f(0, 0, 0)=f(0, 1, 0)=f(1, 0, 0)=f(1, 1, 0) =0. Очевидно, что указанное соответствие действительно взаимнооднозначное: каждая булевая функция f от n переменных задает подмножество Af={(x1, ..., xn)|f(x1, ..., xn)=1} вершин Bn. Например, функция, тождественно равная 0, задает пустое множество Табличное представление Булевы функции от небольшого числа аргументов удобно представлять с помощью таблиц. Таблица для функции f(x1, ..., xn)имеет n+1 столбец. В первых n столбцах указываются значения аргументов x1, ..., xn, а в (n+1) -ом столбце значение функции на этих аргументах - f(x1, ..., xn).
Наборы аргументов в строках обычно располагаются в лексикографическом порядке:
Если эти наборы рассматривать как записи чисел в двоичной системе счисления, то 1-ая строка представляет число 0, 2-ая - 1, 3-я - 2, При больших n табличное представление становится громоздким, например, для функции от 10 переменных потребуется таблицас 1024 строками. Но для малых n оно достаточно наглядно. Формулы Как мы видели, геометрическое и табличное представления булевых функций подходят лишь для функций с небольшим числом аргументов. Формулы позволяют удобно представлять многие функции от большего числа аргументов и оперировать различными представлениями одной и той же функции. Пусть Определение 3.2. 1. Базис индукции. Каждая переменная 2. Шаг индукции. Пусть Каждой формуле Базис индукции. Пусть Шаг индукции. Пусть Далее мы будем рассматривать формулы над множеством элементарных функций Определение 3.3. · Базис индукции. 0, 1 и каждая переменная · Шаг индукции. Пусть Тогда выражения В соответствии с этим определением выражения Для определения функции, задаваемой формулой, удобно использовать таблицу, строки которой сответствуют наборам значений переменных, а в столбце под знаком каждой логической связки стоят значения функции, задаваемой соответствующейподформулой. Свойства логических операций Логические операции Простейшим и наиболее широкоприменяемым примером такойалгебраической системы являетсямножество B, состоящее всего из двухэлементов: B = { Ложь, Истина }. Как правило, в математическихвыражениях Ложь отождествляется слогическим нулём, а Истина — слогической единицей, а операцииотрицания (НЕ), конъюнкции (И) идизъюнкции (ИЛИ) определяются впривычном нам понимании. Легкопоказать, что на данном множестве Bможно задать четыре унарные ишестнадцать бинарных отношений, представленных в таблице справа, однако все они могут быть полученычерез суперпозицию трёх выбранныхопераций. Опираясь на этот математическийинструментарий, логика высказыванийизучает высказывания и предикаты. Также вводятся дополнительныеоперации, такие как эквивалентность Логика высказываний послужилаосновным математическиминструментом при созданиикомпьютеров. Она легко преобразуетсяв битовую логику: истинностьвысказывания обозначается однимбитом (0 — ЛОЖЬ, 1 — ИСТИНА); тогдаоперация Впоследствии булева алгебра была обобщена от логики высказываний путём введения характерных длялогики высказываний аксиом. Это позволило рассматривать, например, логику кубитов, тройственную логику(когда есть три варианта истинности высказывания: «истина», «ложь» и «не определено») и др. -- Популярное:
|
Последнее изменение этой страницы: 2017-03-08; Просмотров: 1926; Нарушение авторского права страницы