Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
В.36 Тождественные высказывания.
• Среди сложных высказываний особое место занимают те, в таблице истинности которых либо одни единицы, либо только нули. Это означает, что истинность высказывания постоянна: оно либо всегда истинно, либо ложно, независимо от истинности входящих в него простых высказываний. • Например, высказывание всегда истинно, а высказывание всегда ложно. • Доказать это можно составив таблицу истинности этих высказываний. Тождественно истинные и тождественно ложные высказывания • Сложные высказывания, истинные при любых значениях входящих в них других высказываний, называются тождественно истинными, а высказывания, ложные при любых значениях входящих в них других высказываний, называются тождественно ложными. • Тождественно истинные или тождественно ложные высказывания, если они встречаются в формулах, заменяются в них, соответственно единицей или нулем
Таблицы истинности для функций тождества
• Тождество может применяться и к унарным операциям (Х)=Х всё кроме, всё за исключением, только и именно Эквивалентные высказывания • Среди высказываний встречаются такие, таблицы истинности которых совпадают. Эти высказывания называются эквивалентными. 2 сложных высказывания считаются эквивалентными, если они принимают одинаковые значения истинности при одинаковой истинности входящих в них простых высказываний. Составим таблицы истинности
Пример: Y1=A+B & C; Y2 = (A+B)& (A+C)
Функционально полная система • Сколь угодно сложную функцию (высказывание) можно записать с помощью ограниченного набора элементарных функций, представляющих собой функционально полную систему логических функций. • Функционально полной системой – базисом – называется система, содержащая конъюнкцию, дизъюнкцию и инверсию. Функционально-полные базисы (ФПБ) • Система булевых функций W называется функционально-полной, если произвольная булева функция вида f (x1, x2, ..., xn) может быть представлена суперпозицией функций x1, x2, ..., xn и суперпозицией конечного числа функций системы W. • Функционально полная система логических функций представляет собой набор логических функций, с помощью которых можно записать любую, сколь угодно сложную функцию. В этом случае говорят, что этот набор образует базис. Функционально полными являются 3 базиса: • 1) " И-ИЛИ-НЕ" (базис конъюнкции, дизъюнкции, инверсии) • 2) " И-НЕ" (базис Шеффера) • 3) " ИЛИ-НЕ" (базис Пирса или функция Вебба).
В.37 Законы алгебры логики • Закон тождества: А=А Всякое высказывание тождественно самому себе • Закон противоречия: Высказывание не может быть одновременно истинным и ложным, т.е. если А=1, то Ø А=0 • Закон исключающего третьего: Высказывание м.б. либо истинным, либо ложным (третьего не дано)
Законы логики • Закон двойного отрицания: • Если дважды отрицать высказывание, то в результате получится исходное высказывание:
Свойства базиса • Свойство констант: с
Формулы Августа де Моргана:
оба эти правила обобщаются на любое число переменных: Свойства базиса • Коммутативность: ХУ=УХ • Ассоциативность: Х(YZ)=(XY)Z • Идемпотентность: XX=X • Дистрибутивность: X(Y+Z)=XY+XZ • Свойство констант: X& 1 = X; • X& 0 = 0;
Свойства базиса • Коммутативность: X+Y = Y+X • Ассоциативность: Х+(Y+Z)=(X+Y)+Z • Идемпотентность: X+X=X • Дистрибутивность: X+YZ=(X+Y)& (X+Z) • Свойство констант: X+1=1 • X+0=X Особенности тождественных преобразований логических функций (в базисе) • Закон поглощения: XÚ X& Y = X; X& (XÚ Y)=X Доказательство: • XÚ X& Y = X& (1Ú Y)=X& 1=X • Закон склеивания: X& YÚ X& Y = X
• Доказательство: Понятие минимизации • Преобразование функции с целью упрощения их аналитического представления называется минимизацией. (Минимизировать формулу сложного высказывания, значит более просто изложить мысль)
Совершенные формулы высказывания • Если формула сложного высказывания представляет собой дизъюнкцию конъюнкций простых высказываний и их инверсий, то она записана в дизъюнктивно нормальной форме.
• X2 отличается от Х1 и Х3 тем, что в состав каждой дизъюнкции входят не все буквы, Х1 и Х3 представлены в совершенной ДНФ (СДНФ) • 1. Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию. • 2. Все логические слагаемые различны. • 3. Ни одно слагаемое не содержит одновременно переменную и ее отрицание. • 4. Ни одно слагаемое не содержит одну и ту же переменную дважды. • Каждой не тождественно ложной формуле соответствует единственная формула с такими свойствами. • Для одной и той же формулы можно составить множество равносильных ей ДНФ. Но среди них существует единственная ДНФ с перечисленными свойствами совершенства. • ДНФ, для которой выполняются свойства совершенства называется совершенной ДНФ (СДНФ). |
Последнее изменение этой страницы: 2017-03-14; Просмотров: 781; Нарушение авторского права страницы