Математика. Раздел 1. Дискретная математика. Тетрадь 1.2. Казанцев Э.Ф. - 30 стр.

UptoLike

ВУЗ: 

МУМ | Москва

Составители: 

Рубрика: 

При мер 2. Вы чис лим фор му лу (X
1
ÉX
2
) Ú ØX
3
(таб ли ца 1.5.7).
Таб ли ца 1.5.7
X
1
X
2
X
3
X
1
ÉX
2
ØX
3
(X
1
ÉX
2
)ÚØ X
3
И И И И Л И
И И Л И И И
И Л И Л Л Л
И Л Л Л И И
Л И И И Л И
Л И Л И И И
Л Л И И Л И
Л Л Л И И И
9) Упо ря до чен ный на бор вы ска зы ва тель ных пе ре мен ных <X
1
..., X
n
>
на зы ва ет ся спи ском пе ре мен ных фор му лы A, ес ли все пе ре мен ные фор -
му лы A со дер жат ся в этом на бо ре. Часть пе ре мен ных мо жет быть фик -
тив ной (из бы точ ной), то есть не вхо дить в фор му лу A. Оцен кой спи ска
на зы ва ет ся со пос тав ле ние ка ж дой пе ре мен ной спи ска не ко то ро го ис -
тин но ст но го зна че ния. Ес ли спи сок со дер жит k пе ре мен ных, то име ет ся
2
k
раз лич ных оце нок. Сле до ва тель но таб ли ца ис тин но сти этой фор му лы
име ет 2
k
строк.
10) Пусть A и B — две фор му лы, за ви ся щие от од но го и то го же
спи ска пе ре мен ных <X
1
, ..., X
n
>. Бу дем на зы вать их рав но силь ны ми, ес -
ли на лю бой оцен ке спи ска <X
1
, ..., X
n
> они при ни ма ют оди на ко вые зна -
че ния. Рав но силь ность обо зна ча ет ся A = B. Нуж но раз ли чать сим во лы ~
и =. Так, ~ яв ля ет ся сим во лом фор маль но го язы ка, с по мо щью ко то ро го
стро ят ся фор му лы, а сим вол = за ме ня ет сло во «рав но силь но».
1.5.3 Ос нов ные рав но силь но сти
а) Бу ле ва ал геб ра:
1) A & B = B & A (ком му та тив ность от но си тель но &).
2) A & A = A (идем по тент ность от но си тель но &).
3) A & (B & C) = (A & B) & C (ас со циа тив ность от но си тель но &).
4) A Ú B = B Ú A (ком му та тив ность от но си тель но Ú).
5) A Ú A = A (идем по тент ность от но си тель но Ú).
30
      Пример 2. Вычислим формулу (X1 ÉX2) Ú ØX3 (таблица 1.5.7).
      Таблица 1.5.7

     X1        X2         X3       X1ÉX2       ØX3      (X1ÉX2)ÚØ X3
     И         И          И          И          Л            И
     И         И          Л          И          И            И
     И         Л          И          Л          Л            Л
     И         Л          Л          Л          И            И
     Л         И          И          И          Л            И
     Л         И          Л          И          И            И
     Л         Л          И          И          Л            И
     Л         Л          Л          И          И            И

       9) Упорядоченный набор высказывательных переменных 
называется списком переменных формулы A, если все переменные фор-
мулы A содержатся в этом наборе. Часть переменных может быть фик-
тивной (избыточной), то есть не входить в формулу A. Оценкой списка
называется сопоставление каждой переменной списка некоторого ис-
тинностного значения. Если список содержит k переменных, то имеется
2k различных оценок. Следовательно таблица истинности этой формулы
имеет 2k строк.

      10) Пусть A и B — две формулы, зависящие от одного и того же
списка переменных . Будем называть их равносильными, ес-
ли на любой оценке списка  они принимают одинаковые зна-
чения. Равносильность обозначается A = B. Нужно различать символы ~
и =. Так, ~ является символом формального языка, с помощью которого
строятся формулы, а символ = заменяет слово «равносильно».

      1.5.3 Основные равносильности

      а) Булева алгебра:
      1) A & B = B & A (коммутативность относительно &).
      2) A & A = A (идемпотентность относительно &).
      3) A & (B & C) = (A & B) & C (ассоциативность относительно &).
      4) A Ú B = B Ú A (коммутативность относительно Ú).
      5) A Ú A = A (идемпотентность относительно Ú).
30

Страницы