Ш.И._Галиев_МЛ_и_ТА_2004

знака & связывает наименьшие формы, окружающие это вхождение; затем (т.е. после расстановки всгх скобок, относящихся ко всем вхож­ дениям знаков 1 н &) каждое вхождении знака v связывает наимень-

При применении этого правила к одной и той же связке продвигаемся

Пример. В форме As ..4&3=sCvl D скобки восстанавливаются

■4=(l-4)&B^.Cv<lD); Л.«14)&Я)^СМ1й); ^.((V)&B)=>(Cv(l0)); Л-(({1Л)&В)=*{СМЪ)));

(АЦ!.(\Л)ЬВ)^(С.>{\D)))).

Однако не всякая форма может быть записана без скобок. Например, нельзя опустить гатившиеся скобки в формах: А&(В=$С), А = -(8^0, \.4vB).

Приходится порой простые иысяи

ппкаэь:ятть всеръа\ каятгор&ми,

1 4. Тавтологии (общезначимые формул!,i). Нротньпречня

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

Таблица истинности тавтологии имеет результирующий сюл-

Примером тавтологии является пропозициональная форма Л\Аа , в чем легко убедиться, составив таблицу истинности. Другие примеры тавтологий\A=>A,(A-B^{BsA). '

21

	Противоречием (тождественно лютой пропозициональной
формой) называется пропозициональная форма, принимающая
значение Л при любой совокупности истинностных значений пропо­
зициональных бука, входящихе нее.
.	Примеры противоречий: А& 'A, l(A=*A), Ая^А.
	Истинностная таблица для противоречия, очевидно, имеет
6 результирующем столбцетолько значения.?.
	Очевидно, что пропозициональная форма Л является тавтолож-
сй тогда и только тогда, когда~\а естьпротиворечие.
	Тавтологиюбудемпбоэначагьчерез Г, о противоречиечерезЯ.
	Сформулируем ндокажемляе несложныетеоремы.
|	Теорема1,1. Если^иАоЗ- гавгологаи.тиД--тмяология.	|

Доказательство. ПустьА и А ^В -тавтологии. Допустим, что при .некоторой распределении истинностных значений для пропози­ циональных букс, входящих з А н В, В принимает зшчмпю Л. По­ скольку А есть тавтология, то при этом распределении истинностных значений А принимает значение Д. Тогда А=>В получит иючепие Л Это противоречит предположению о том, что А—,В есть тавтология.

Теорема 1.2. ЕслиА есть тавтология, содержащая пропозицио­ нальные буквы At, А},..., Ас, и В получается из А подстановклй в А пропозициональных форч А,, А],... А„ вместо буке Аь /I;... А, соот­ ветственно, то В sen. тавтология, т.е. подстановка п тавтологию при­ водит К ТАВТОЛОГИИ.

	Доказательство. Пусть задано произвольное распределение
истинностных значений дм		пропозициональных букв,		входящих
в В. Формы А.,Аг,-.,А„		примут тогда	некоторые	значения
*1.	*.> (каждое х, есть	И или Л). Если	придадим	чщченив

22

ij, х„ соответственно буквам Ab A-t. ... А,, то так как А есть Тав­ тологии, та А будет истинно, и это же знамение принимает В.

Таким образом, при произвольных значениях пропозициональ­ ных букв форма В принимаетзначение И, чтои требовалось доказать.

Ясно, что при подстановке в пропозициональную форму вместо пропозициональных букв высказываний, получим некоторое высказы-

Высказывание, которое получается из какой-либо тавтологии посредством подстановки высказываний вместо пропозициональных буки при условии, чти вхождение одной и той же буквы замещается одним и теп же высказыванием, называется логически истинным высказыванием. Это высказывание истинно в силу своей формы, а не в силу своего содержания, Например, высказывание. "Если Ива­ нов студент, то Иванов - студент" всегда истинно (логически истин­ но), в ТОвремя так высказывание "Ивакоп. - студент", если и истинно, то всилу уже других причин.

Высказывание, которое можно получить с помощью подстанов­ ки в противоречие, называется логичеатложным высказыванием. Его примером может служить высказывание; ''2х2“4 и 2x2*4", где имеет место одновременно какое-то высказывание и отрицание этого же вы-

Продозициональная форма называется выполнимой, ели она принимает значения И хоти бы для оцкоВ совокупности значений пропозициональных букв, в нее входящих,

Например, A&J3 является выполнимой пропочиииокальнпй фор­ мой, так как принимает значения Я, когдаЛ-И и В=И, а форма A&U не будетвыполнимой, так как всегда ложна,

я только тогда, когдаА не является противоречием. ИроОпемаразрешимости (логики пиекялмваний) состоит в сле­

дующем: существует лн правило, позволяющее для каждой пропози­ циональной формы А конечным числом действий выяснить, является Л выполнимой или нет.

23

Ясно, что выяснение выполнимости А равносильно амкскению, является ли А противоречием или нет, что, в свою очередь, равно­ сильно выяснению, является ли "U тавтологией или нет. Такам обра­ зом, если еста метод, позволяющий для произвольной формы конеч­ ным числом девотий выяснить, тавтология это или нет, то можно решить вопрос - выполнима илинет произвольная формаЛ. Для этого достаточно выяснить \л -тто ло гм или нет, Бели А - тавтология, го 4 - протипоречке, следовательно, А невыполнимо, если же 1 А - не тавтология, то А выполнимо.

Проблема разрешимое™ (логики высказываний) полностью ре­ шается, например, с помощью таблиц истинности. Если пропозицио­ нальная форма содержит п различных букв, то, как известно, ее таблиц*, истинности имеет 2’ строи. При больших значениях и составление таблиц исганносгя и выяснение выполнимости по ним является громоздкой операцией. Для решения проблемы раз­ решимости существуют и другие способы, оспоапнные на приведении к так называемым нормальным формам. Эта формы и способы реше­ ния а ихномощыо проблемырвзреншмоггибудутрассмотрены.

Какде.тииенртккуСпеякШоках.

Иновр/жкуШшал прмлпткч ислыкам,

ЛCodeтолькойяюдвчмдалс облд*м.

Тыsossмисебеяожку. я - вшкчинижи

Ипоиши:», у»екя Шакаяпа юраеу,

Л.Кзр?01и*

§ S. Равносильность проп<ншшоиа.львых форм

Пропозициональные формы А и В называются равносильными, если при каедой совокупности значений всех пропозициональных

sперсаам С.Маршака,Д. ОрдошгаИ яО. Севдпюё.	?
24

	Например, форма "UvJJ		ьна форме А^В, в чем
убедиться с помощьютаблицк
•'	А		.4	=■	В
И	Л	И			Л
И	.7	и	Л	и	И
Л	И	п	я ■	л
Л	И	я			К

В »ю	таблицах резуттирующие столб UJ совпадают, т е. при
одни ковых	ачени® буквА		знач ния форм 1 AvB и Д=?Д равны.
еле,41ватель	■VTHформы ран		илън	. Далее, форма 4vA&fl равно-
енльнаАД	твител но, имее		-ледугашкетаблицы:
*		/)	4	В
Л		Л	Л	л
л		Л		и		Л
я	И	Я	,7	л		и
и	Я	и	И	и		н
Также,	цевпдн , Av]A		НОСИ. ьно5*1ъ .
Up* опрелелении равно				II двух форм		е обязательно
предполагат	что они содерж		ЛИИ	те же пропозиционяльк ге 6у-
квы. ак, в		првмер	имеем случаи когда в рвение				1ьные
формы вход	разные буквы.		1ри этои, есл		акнл-нийуд1 прппози-
ЦИОН льная ь		дит толь	в одн ' из л		х равносильных форм,
то эта форм	при все	значениях этой буквы принимает одно и то же
значение, е	и значе ИЯ друг		фиксИрОБШ		Следоватгяьн		X0T9
яв буква г входит в		юрму.	СТИН10ST1KD <уш<ци«			опреде. енпая
фЭрЫ и, от .ачений		гой букв	независит.

Высказывание "А равносильно В" будем обозначать следующим

Пусть А, В, С - произвольные Пропозициональные фирмы. От­ ношение равносильности пропозициональных форм, как легко пинать, обладает следующими свойствами:

1 )А ~А - рефлексивность;

3) если А - В и В - С .тоЛ - С- транзитивность. Следовательно, отношение равносильное™ является отношени­

ем эквивалентности и порождает разбиение мношествя пропозицио­ нальных форм на напересекающиеся клаесм. В каждый ю;лсс попщиеот равносильные между собой пропозициональные формы. Докажем

Теорема J.S. Пропорциональные формы Л н i югда и только тогда, когдаА^В являетсятавтологией.

Доказательство. Необходимость. Пусть А и В равносильны, следовательно, онв лри каждой совокупностк значений всех пропози­ циональных букв, входгших в них, принимают одинаковые истинно­ стные значениятогда ло определению связки ~ форма A-R всегда принимает значение И, т.е. юталя тавтологией.

Досгточность. Пуссь AsB тавтология, т.е. принимает всегда значение И. Это означаем чтоА и В имеют всегда одинаковые истин-

§ 6, Важнейшие пары равносильных пропозициональных форм

ПустьА. В С-нротхвинипналывдебуквы, Г-тавгология иУ7-про­ тиворечие. Используятаблицуистинности,легкопоказать:

1) 1(1/!) равносильно Л.

26

Если под А понимать обозначение некоторого высказывания, то получаем, что двоЯшг отрицание высказывания л означает та же, т а

к высказывание А. Полученное соотношение между 1(1Л) иА называют закона,и двойного Отрицания.

Лналогичньы образом можио показать, что имеют место следующие законы;

2)Л&Л-Я&Л]

4)(А&В)&С~А&(В&С)'i - закона жсоииативности;

5) (Av B)-vC~ A 'j(B ^C ) j ^

6) .4&fZJvCj ~ A&frjA&.C- первыЯэакондистрибутивности ’) AvB&C~ (AvB)&(A~/C) - второйзакон дистриОутивмхти,

) 1(А&В) —l^ v l		Я	"j
			J - законы деМоргана;
)	Л&А 'А ,
)	А'./Л ~А, J*	— зякопы идемпотентности;

Л&! А - П - jaxoit’ протилоргчия; ) А&.Т-Л

( v r - T

16)Л&П-П

17)А Л 1-А

Щ АчАЬВ-А

19)А&(АмП)-А

20)А-s В-1 U=s'А ■— мком кантовтюз-,

Как уже замечено, ссштношения 1) -20) Д|

27

равносильные упрошенные фермы или равносильные формы, имею­ щиеболе«удсйний с некоторыхпозиций Рид.

Из соотношений2J - 6) видно, что операция & напоминает ум­ ножение (обладает некоторыми свойствами умножения), a v - сложе­ ние, поэтому часто конъюнкцию двух выскиланий называют(логи­ ческий) произведением их, а дизъюнкцию-(логической) суммой.

Склт двух, ктонебылвк

§ 7. Зависимости между пропозициональными связками

Связки 1, V, - к: являются независимымидруг от друга я том смысле, что один из них можно выражап. через другие, такчто при этом получаются равносильные пропозициональные фор-

Например, «взка « может быть выражена через связки w и & на основаниисоотношения

As£-(A^S)&{BnA). ( 1.1)

Дла доказательства (1.1) достаточно составить таблицы истин­ ности и убедиться, что реулътирующне столбцы этих таблиц совпа-

Для импликацииимеем:
A»B~~\AvB.	(1.2)
Таким образом,связкув можно выразить через *1,ft и v ;
jl*fi~<l-4vJJ)&(]Bvi<).	(1.3)
Та* как А равносильно 1(1.4), то А&Я равносильно
(U), . п .,<Щт, согласно закону де Моргана	равносильно
1(1/1 vlS), следовательно,

28

	А& в- 1<;Л'-ЛЯ	<1.4)
	Легко видеть, ято имеем:	0.5)
	-dvS-
	М}соотношеии»(1.2) заменой ~\АнаА получаем, что	(1.6)
	АчВ~1 а=>В.
!	Теорема 1.4. Для каждой пропозициональной формыА сушест-1

lojre'f равносильная ей форма, содержащая только связки 1, &, v i

Доказательств. Связки =■ н в можно исключить согласно сосгтошшиям (1.2) и (1.3). При этом останутся -«шько связан 1, &, V. Если пропозициональная связяа 1 стоит перед некото­ рой скобкой, например, 1(Л&ЙуС\'13), то на основании законов деМоргана можно внести 1 под скобки, при >том связка & меняется

скобки, перед которыми они стоят, добьемся, чтобы I относилась

Теорема I.S. Дчн каждой пропозициональной формы А сущесг-

»ует равносильная ей форма, содержащая либо только свяжи 1, 4,

соотношений (1.2) и (1.3),	а затем по (1.5) исключим v.
Н результате останутся только 1	н4. Остальные случаи доказывают­
ся аналогичным образом на основании соотношений(1,1)-(1.6).
Будем рассматривать пропозициональные формы, содержащие

только связки 1 , &, у. Как уже установлено, всякая проттозициональ-

нал форма может быть приведена преобразованиями роипоснлыюсти ктакому виду.

Будем говории, чтосвазка & дшапветасвяш v , и наоборот. Пропорциональные формыА и.4*называются двойственными,

если одна получается издругойзаменой каждой связки &и i/на двой­ ственную.

Например,ест А Н М Ш С .-ю А ' =(Л &lB)vC.

А* двойствен» А. Следующую теорему считают законом двойтвенност.

Теорема 1.6. Если пропозициональные формы А и В равно­

сильны, га идвойственные ич формыА* и 8* также равносильны.

Доказательство, Пусть А г В равносильны, a А\,А]....,А» - буквы, входящие в А или В. Будем считать, что АьАъ-М входи и в Л, и в В. Еолн 5н лъ бы^о не так, например, Б не содержала бы /fi(l£fe«j, входящего в А, то В можно заменить равносильной

формой	содержащейsry букву.
Таким образом, лесгаа можем добиться, чтобыА я В содержали
По условию
A<A-l,Ai ...,Ar)~B(A„A1,..,A,).		'	(17)
Если формы А н В равносильны, те, очевидно, равносильны
иих отрицания, поэтому из(1.7) получим, что
1	/<(4,J V ..A )~"IB(,M I ...A}.		0-8)
В прошвициопальвы* формах :оотнтпския (1.8) добьемся,
чтобы !	относилась только к буквам. При этом согласно законам

де Моргаю связки & н v поменяются на двойственные. Следо­ вательно, получим

Л

1А/у

(1.9)

30