![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Булева алгебра высказываний (алгебра логики)Содержание книги Поиск на нашем сайте
Высказыванием об элементах множества U называется любое утверждение об элементах множества U, которое для каждого элемента либо истинно, либо ложно. U = {1 2 3 4 5 6 7 8 9}
A = «число четное» B = «число, меньшее пяти»
Множеством истинности высказывания называется совокупность всех элементов, для которых это высказывание истинно.
SA = {2 4 6 8} SB = {1 2 3 4}
Высказывание, для которого множество истинности пусто, называется тождественно ложным, а для которого SB = U называется тождественно истинным. Высказывания, для которых множества истинности совпадают, называются тождественными или равносильными. Равносильные высказывания объединим в один класс Р.В. и не будем их разделять, т.к. все они имеют одно и то же множество истинности.
Операции над высказываниями Дизъюнкция высказываний (V, ИЛИ, OR) Дизъюнкция высказываний – высказывание, истинное тогда, когда истинно хотя бы одно из высказываний. Конъюнкция высказываний (&, И, AND). Конъюнкцией высказываний называется высказывание, истинное тогда и только тогда, когда истинны все высказывания. Отрицание высказываний (- над буквой, НЕ, NOT). Отрицанием высказывания называется высказывание, истинное только тогда, когда исходное высказывание ложно.
Л – ложно. И – истинно.
Утверждение (основа всей алгебры логики) Между множеством всех классов эквивалентных высказываний об элементах множества U и множеством P(U) можно установить взаимно однозначное соответствие, при котором операция дизъюнкции высказываний соответствует операции объединения множеств истинности, а конъюнкция соответствует операции пересечения. Операция отрицания соответствует операции дополнения. Следствие. Множество классов эквивалентных высказываний является булевой алгеброй. Теорема Существуют 3 булевых алгебры: 1. P(U) 2. Bn 3. Множество классов эквивалентных высказываний. Три булевых алгебры являются изоморфными, если между их элементами можно установить такое однозначное соответствие, при котором операции сохраняются.
Договоримся конъюнкцию обозначать точкой (как знак умножения в алгебре чисел). Конъюнкция выполняется раньше дизъюнкции (аналог выполнения операций сложения и умножения в алгебре чисел).
Лекция 3 Определение и способ задания булевых функций
Булевой функцией от n аргументов называется однозначное отображение n – мерного булева куба на одномерный булев куб.
Способы задания функций 1. Табличный
gi - значение функции от данных аргументов. Порядок возрастания векторов по мере возрастания их номеров называют лексикографическим. 2. Векторный F = (g1...gn) 3. Геометрический Единичным вектором для данной функции называется тот вектор, значение функции на котором равно 1. Носителем данной функции – совокупность всех единичных векторов этой функции (Nf – носитель функции f)
Nf = {001, 011, 100, 110} = [1,3,4,6] [] – указаны номера векторов.
3. В виде формулы. Функция f зависит от переменной xi фиктивно, если для любых двух наборов значений переменных, отличающихся только значением переменной xi, значения функции f совпадают. Будем говорить, что f зависит от переменной xi существенно, если существуют такие два набора значений, отличающихся только значением переменной xi, на которых значения функций различно. Фиктивные переменные у функции можно добавлять и исключать. Две булевы функции называются равными или равносильными, если одну можно получить из другой путем добавления и изъятия фиктивных переменных.
Строим таблицу функций при n = 1.
Таблица всех элементарных булевых функций, применяемых в записи формул
Все эти функции от двух аргументов мы и будем называть элементарными булевыми функциями.
Основными элементарными функциями являются конъюнкция, дизъюнкция и отрицание. Элементарные булевы функции удовлетворяют всем аксиомам булевой алгебры. Суперпозиции булевых функций Ф = {ф1…фk}
F называется элементарной суперпозицией функции из множества Ф, если она получена одним из следующих способов. 1. Переименование какого-нибудь аргумента в одной из функций системы (возможно отождествление аргумента). 2. В одну из функций системы вместо любого аргумента ставится значение любой функции из этой системы.
Ф1 = {Y…xn} Фi = (x1 … фj(x1…xn) … xn)
Ф(1) – множество всех элементарных суперпозиций из системы Ф. Ф(k+1) – множество всех элементарных суперпозиций из систему Фk.
Функция g называется суперпозицией функций из системы, если $ N: g Î Фn Это означает, что g можно получить из функции системы Ф, применяя конечное число раз операцию элементарной суперпозиции. Конкретное выражение суперпозиции будем называть формулой над системой Ф. G = Fф Суперпозиция элементарных булевых функций – формула. Для удобства записи договоримся, что отрицание – самая сильная операция. Следующая – конъюнкция, а остальные – равносильны. _ _ X+Y = XY V XY _ _ X ~ Y = XY V XY __ X ® Y = X V Y _ _ X ¯ Y = X Y Лекция 4
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-04-18; просмотров: 334; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.216.131.64 (0.009 с.) |