В.36 Тождественные высказывания.

• Среди сложных высказываний особое место занимают те, в таблице истинности которых либо одни единицы, либо только нули. Это означает, что истинность высказывания постоянна: оно либо всегда истинно, либо ложно, независимо от истинности входящих в него простых высказываний.

• Например, высказывание всегда истинно, а высказывание всегда ложно.

• Доказать это можно составив таблицу истинности этих высказываний.

Тождественно истинные и тождественно ложные высказывания

• Сложные высказывания, истинные при любых значениях входящих в них других высказываний, называются тождественно истинными, а высказывания, ложные при любых значениях входящих в них других высказываний, называются тождественно ложными.

• Тождественно истинные или тождественно ложные высказывания, если они встречаются в формулах, заменяются в них, соответственно единицей или нулем

 

 

Таблицы истинности для функций тождества

 

• Тождество может применяться и к унарным операциям (Х)=Х всё кроме, всё за исключением, только и именно

Эквивалентные высказывания

• Среди высказываний встречаются такие, таблицы истинности которых совпадают. Эти высказывания называются эквивалентными. 2 сложных высказывания считаются эквивалентными, если они принимают одинаковые значения истинности при одинаковой истинности входящих в них простых высказываний.

Составим таблицы истинности

 

 

 

Пример: Y1=A+B & C; Y2 = (A+B)& (A+C)

	A	B	C	B& C	Y1	A+B	A+C	Y2

 

Функционально полная система

• Сколь угодно сложную функцию (высказывание) можно записать с помощью ограниченного набора элементарных функций, представляющих собой функционально полную систему логических функций.

• Функционально полной системой – базисом – называется система, содержащая конъюнкцию, дизъюнкцию и инверсию.

Функционально-полные базисы (ФПБ)

• Система булевых функций 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. Ни одно слагаемое не содержит одну и ту же переменную дважды.

• Каждой не тождественно ложной формуле соответствует единственная формула с такими свойствами.

• Для одной и той же формулы можно составить множество равносильных ей ДНФ. Но среди них существует единственная ДНФ с перечисленными свойствами совершенства.

• ДНФ, для которой выполняются свойства совершенства называется совершенной ДНФ (СДНФ).

⇐ Предыдущая567891011121314Следующая ⇒

Поделиться: