Алгебра логикасының формулалары.  Тұжырымдар логикасының құрылымын зерттейтін алгебра логикасының

20 
е) Шеффер штрихы
 
(антиконъюнкция). Белгіленуі 
y
x
.
Анықтама бойынша 
)
(
)
(
y
x
y
x



немесе 
)
(
)
(
y
x
y
x


; 
ж) Пирс стрелкасы
 
(антидизъюнкция). Белгіленуі 
y
x

.
Анықтама бойынша 
)
(
)
(
y
x
y
x




немесе 
)
(
)
(
y
x
y
x



; 
и) сақиналы қосынды (логикалық қосу, модуль екі бойынша қосу). 
Белгіленуі 
y
x

. Былай анықталады: 
)
(
y
x
y
x




немесе 
)
~
(
y
x
y
x


. 
Осы операциялардың ақиқаттық кестесін құрамыз.
2.1.3 кесте 
x
y
y
x
y
x

y
x

0 
0 
1 
1 
0 
0 
1 
1 
0 
1 
1 
0 
1 
0 
1 
1 
1 
0 
0 
0 
Тепе-тең түрлендірулермен формулалар жасағанда қисаптардың 
орындалу ретін (қайсысы күштірек, қайсысы әлсіз) сақтаған жөн. Бұл жағдай 
үшін келесі келісімдер қабылданған:
а) сыртқы жақшаларды жазбауға болады, мысалы, 
)
)
((
z
y
x


орнына 
z
y
x


)
(
; 
б) логикалық қисаптардың орындалу ретін: 













,
,
,
,
|,
,
,
, 
мұндағы қисаптардың таңбалары ең мықтысынан бастап кему ретімен 
жазылған, ал жай жақшада күші бірдей қисаптар көрсетілген. 
Осы келісімдер бойынша формуладағы жетпей тұрған жақшаларды 
күштіден әлсізіне қарай біртіндеп қояды. Ал күші бірдей байланыстар үшін
жақшалар солдан оңға қарай қойылады. 

Мысалы 2.1.3
- а) 
u
z
y
x



формуласындағы жақшалар былай 
қойылады: 
)
(
)
(
u
z
y
x



; б) 
)
(
z
y
x


формуласында жақшаларды алып 
тастауға болмайды, себебі келісімдер бойынша 
x
y
z
 
өрнегіне 
(
)
x
y
z


формуласы сәйкес келеді. 
Алгебралар логикасының функциялары. 
Әрбір формула логикалық айнымалылы логикалық функцияны білдіреді, 
олар тек екі мән қабылдайды 0 және 1.

Анықтама.

 
n
x
x
x
,...,
,
2
1
-
n 
айнымалылы алгебралар логикасының
функциясы 
(
логикалық функция
) 
деп 
(
белгіленуі
)
,...,
(
1
n
x
x
f
) 
)
,...,
,
(
2
1
n



бірлер 
мен нолдердің кез келген жиынтығына 
}
1
,
0
{
)
,...,
,
(
2
1

n
f



мәнін сәйкес қоятын, 
яғни 
}
1
,
0
{
}
1
,
0
{
:

n
f
кез келген функция айтылады. 
Алгебралар логикасының функциялары буль, екілік немесе ауыстырып-
қосқыш
 
(белгіленілері 
n
P
n
P
P
),
(
,
2
2
). функциялары деп те аталады. Бұл 
функциялар кейбір құрылғылардың ену сигналдарын шығу сигналдарына 

21 
айналдыру үшін қолданылады. Құрылғыда 
n
x
x
x
,...,
,
2
1
- 
n
ену сигналы бар 
болсын. Олар арқылы ток жүруі де, жүрмеуі де мүмкін. Шығу жолы да біреу, 
кіру жолда ток жүргеніне байланысты ол арқылы ток жүруі де, жүрмеуі де 
мүмкін (2.1.1 суретті қара).
2.1.1 сурет 2.1.2 сурет 
1

i
x
мәнінің берілуін 
i
-ші кіру жолда ток берілді деп түсінеміз; 
0

i
x
- 
ток берілме. Егер кіру жолда ток жүрсе, онда 
1
)
,...,
,
(
2
1

n
f



(мұндағы 
n
n
x
x




,...,
1
1
) және 
0
)
,...,
,
(
2
1

n
f



- егер ток жүрмесе. 

Мысалы, конъюнкция қисабымен 

y
x
y
x
f


)
,
(
функциясы екі кіру, бір 
шығу жолы бар қондырғыға сәйкес келеді (2.1.2 суретті қара). Егер кіру жолда 
екі мән де 1-ге тең болғанда, шығу жолдағы мән 1-ге тең болады. 

 
 
Функциялардың берілу әдістері: 
а) ақиқаттық кестесімен беріледі, сол жағында 
n
x
x
x
,...,
,
2
1
 
аргументтердің 
барлық мүмкін мәндерінің жиынтығы жазылған
, 
ал оң жағында – осы 
жиынтыққа сәйкес 
f
функциясының мәндерінің бағаны. Функцияның 
n
айнымалыларының қабылдайтын 0 мен 1-лердің жиынтықтарының саны 
n
2
тең, яғни бір айнымалы функция үшін -
2
2
1

, екі - 
4
2
2

, үш - 
8
2
3

және т.б. 
Сонымен, бір айнымалы функция үшін ақиқаттық кестесімен 2 жолдан, екі – 4, 
үш – 8 және т.б. Аргументтер жиынын лексикографиктік ретпен жазу керек. 
Практически этот порядок можно получить, Егер кестенің бірінші бағанын 
екіге бөлсек, бір жартысына нолдер, екіншісіне бірлер жазамыз. Содан соң 
екінші бағанды төртке бөліп, 0 мен 1-лерді кезекпен қою керек, тек 0-ден 
бастау керек; үшінші бағанды сегіз бөлікке бөліп, 0 мен 1-лерді кезекпен қою 
керек, тек 0-ден бастау керек, т.с.с.; 
 
б) функцияның барлық жиынтықтарын тізіп жазу, ол үшін 
f
-тің 0 мәнін 
қабылдайтын жиынтықтарын (нолдік жиынтық) және 1-ді қабылдайтын 
жиынтықтарын (бірлік жиынтық); 
в) функцияны формуламен беру; 
г) функцияның мәндерінің векторы көмегімен беру. Функцияның 
мәндерінің векторы 
)
,...,
(
1
n
x
x
f
деп 
f
-тың барлық реттелген жиынтықтары 
айтылады, онда 
n
}
1
,
0
{
аргумент жиыны бойынша барлық мәндер 
лексикографиктік ретпен жазылған.
Функциялардың берілу әдістерін да қарастырайық. 
Мысалы 2.1.4
- Үш адам қандай да бір резолюция қабылдау үшін 
қондырғы орнатқан (үштік комитет). Комитеттің әрбір мүшесі резолюцияны 
құптағанда өз кнопкасын басады. Егер көпшілік құптаса, онда резолюция 
1
( ,...,
)
n
f x
x
2
x
n
x
f
y
x


x
y
1
x

22 
қабылданады да, қондырғыда жазылады. Сонымен, қондырғы 
)
,
,
(
z
y
x
f
функциясын іске асырады, оның ақиқаттық кестесі:
2.1.3 кесте 
x 
y 
z 
)
,
,
(
z
y
x
f
0 
0 
0 
0 
0 
0 
1 
0 
0 
1 
0 
0 
0 
1 
1 
1 
1 
0 
0 
0 
1 
0 
1 
1 
1 
1 
0 
1 
1 
1 
1 
1 
Осы функцияны нөлдік және бірлік жиынтықтармен берейік: 
0
)
0
,
0
,
1
(
)
0
,
1
,
0
(
)
1
,
0
,
0
(
)
0
,
0
,
0
(




f
f
f
f
- нөлдік жиынтық;


)
1
,
0
,
1
(
)
1
,
1
,
0
(
f
f
1
)
1
,
1
,
1
(
)
0
,
1
,
1
(



f
f
- бірлік жиынтық. Егер осы функцияны вектор мәні 
бойынша берсек, онда мына түрде болады (00010111). 
Сонымен, 
n
айнымалылы функция үшін 0 мен 1 –дің барлық жиынтық 
саны 
n
2
. 
n
айнымалылы әртүрлі мүмкін функциялар саны
n
2
жолы бар 
бағандардағы 0 мен 1 –дің орналастыру санына тең, яғни
2
2
n
. Егер 
n
n
B
}
1
,
0
{

- 
жиын 
)
,...,
(
1
n
x
x
f
функцияның аргументтерінің барлық мәндерінің жиынын, ал 
)
(
2
n
P
- 
n
x
x
x
,...,
,
2
1

жүктеу/скачать 1,03 Mb.

Достарыңызбен бөлісу: