Т. А. Сливина математическая логика и теория алгоритмов


Закон исключенного третьего: ├



Download 2 Mb.
bet17/57
Sana25.02.2022
Hajmi2 Mb.
#271607
1   ...   13   14   15   16   17   18   19   20   ...   57
Bog'liq
Учебное пособие-Математическая логика и теория алгоритмов

5. Закон исключенного третьего: ├
Доказательство: Воспользуемся доказуемой формулой
├ (10)
и, сделав в ней подстановку , получим
(11)
Также сделаем подстановку в формуле (7), заменяя х на , а у на :
├ (12)
Используя закон соединения посылок, будем иметь
├ (13)
Из формул (11) и (13) по правилу силлогизма получим
├ (14)
Из формулы (14) по правилу контрпозиции следует ├
Используя оба правила снятия двойного отрицания, получаем
(15)
Пусть теперь у – любая доказуемая формула R, тогда из формул ├R и ├ по правилу заключения получаем

6. ├
Доказательство: Сделаем подстановку в аксиоме III3, заменяя в ней z на :
├ (16)
Из аксиом II1 и II2 имеем:
├ (17)
├ (18)
Применяя к формулам (17) и (18) правило контрпозиции, получим
(19)
(20)
Используя правило снятия двойного отрицания, будем иметь:
(21)
(22)
Применяя к формулам (16), (21) и (22) правило сложного заключения, получим
(23)
Применяя к формуле (23) правило контрпозиции, а затем правило снятия двойного отрицания, получаем .


§6. Связь между алгеброй высказываний и исчислением высказываний

Формулы исчисления высказываний можно интерпретировать как формулы алгебры высказываний. Для этого будем трактовать переменные исчисления высказываний как переменные алгебры высказываний, то есть переменные в содержательном смысле, принимающие два значения: истина и ложь (1 и 0).


Операции , , , – определим так же, как в алгебре высказываний. При этом всякая формула исчисления высказываний при любых входящих в нее переменных будет принимать одно из значений 1 или 0, вычисляемое по правилам алгебры высказываний.
Введем понятие значения формулы исчисления высказываний.
Пусть А формула исчисления высказываний, x1, х2, ..., хп – попарно различные переменные, среди которых находятся все переменные, входящие в формулу А.
Обозначим через а1, а2, ..., an набор значений этих переменных, состоящий из 1 и 0, длины n. Очевидно, что вектор (а1, а2, …, аn) имеет 2n значений.
Определим значение формулы А на одном таком наборе значений переменных, обозначая его через :
1. Если для формулы А ее подформула самой большой глубины есть xi, то .
2. Если определены значения всех подформул глубины (k+1), то подформулы глубины k, полученные в результате операций , , и будут иметь значения:
,
,
,
.
Например, формула на наборе значений (0,1,1,0) переменных х1, х2, х3, х4 имеет значение R0110( ) = 1.
Действительно, эта формула имеет:
– подформулы первой глубины,
– подформулы второй глубины,
х4, х2, – подформулы третьей глубины,
х3 – подформула четвертой глубины.
Отсюда R0110 (x3) = 1,
, R0110 (x2) = 1, R0110 (x4) = 0,
=0, , R0110 (x1) = 0,
)= =1,
R0110( )=R0110( )R0110( )=1.

Приведем формулировки теорем, которые устанавливают связь между основными фактами алгебры высказываний и исчисления высказываний.



Download 2 Mb.

Do'stlaringiz bilan baham:
1   ...   13   14   15   16   17   18   19   20   ...   57




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish