 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Основные эквивалентности логики высказываний
(основные тождества алгебра логики)
1. x®y ~ ØxÚy – удаление импликации
2. x 
y ~ xÙy Ú ØxÙØy
x y ~ (ØxÚy) Ù (xÚØy) удаление эквивалентности
3. x Å y ~ ØxÙy Ú xÙØy
x Å y ~ (xÚy) Ù (ØxÚØy) удаление сложения по модулю 2
4. Ø(xÙy) ~ ØxÚØy;
Ø(xÚy) ~ ØxÙØy – законы де Моргана
5. xÙ(yÚz) ~ (xÙy)Ú(xÙz); – дистрибутивность конъюнкции относительно дизъюнкции
6. xÚ(yÙz) ~ (xÚy)Ù(xÚz) - дистрибутивность дизъюнкции относительно конъюнкции
7. xÙx ~ x; xÙy ~ yÙx; xÙ(yÙz) ~ (xÙy)Ùz; – идемпотентность, коммутативность и ассоциативность конъюнкции
8. xÚx ~ x; xÚy ~ yÚx; xÚ(yÚz) ~ (xÚy)Úz; - идемпотентность, коммутативность и ассоциативность конъюнкции
9. xÙ1 ~ x; xÚ1 ~ 1 - операции с константой 1
10. xÙ0 ~ 0; xÚ0 ~ x – операции с константой 0
11. xÙØx ~ 0 - закон противоречия
12. xÚØx ~ 1 - закон исключения третьего
13. xÙ(yÚx) ~ x; xÚ(yÙx) ~ x – законы поглощения
14. ØØx ~ x – закон двойного отрицания
15. (xÙy)Ú(ØxÙz) ~ (xÙy)Ú(ØxÙz) Ú(y Ùz) - правило резолюции
(xÙy)Ú(ØxÙy) ~ y - частный случай – склеивание - расщепление
16. (xÚy)Ù(ØxÚz) ~ (xÚy)Ù(ØxÚz) Ù(yÚz) - правило резолюции
(xÚy)Ù(ØxÚy) ~ y - частный случай – склеивание - расщепление
Теорема (о подстановке). Пусть |= F(Х1, …,Хn), где Х1, …,Хn – список пропозициональных переменных, входящих в F, а А1, …, Аn – список произвольных формул логики высказываний.
Тогда |= F(А1, …,Аn), где F(А1, …,Аn) –результат подстановки формул Аi на место переменных Хi в формулу F(Х1, …,Хn).
Следствие. Пусть F(Х1, …,Хn) ~ G(Х1, …,Хn), где Х1, …,Хn – список пропозициональных переменных, входящих в F и G, а А1, …, Аn – список произвольных формул логики высказываний. Тогда
F(А1, …,Аn) ~ G(А1, …,Аn)), где F(А1, …,Аn) и G(А1, …,Аn) –результаты подстановки формул Аi на место переменных Хi в формулы F(Х1, …,Хn) и G(Х1, …,Хn) соответственно.
Таким образом, основные эквивалентности можно использовать, не только в виде, указанном выше, но и в виде эквивалентностей, получающихся из них подстановками произвольных формул на место пропозициональных переменных x, y, z.
Поиск по сайту: