Тесты по теме 31 VI тарау. Алгоритмдер теориясының ЭлементтерІ 34

жүктеу 8,05 Mb.

бет	44/75
Дата	11.12.2017
өлшемі	8,05 Mb.
	#4014
түрі	Тесты

1 ... 40 41 42 43 44 45 46 47 ... 75

3.6 Пренекстік нормал форма

Анықтама. Егер предикаттар логикасының формуласы терістеу, конъюнкция, дизъюнкция және кванторлық операциялар көмегімен құрылған болса және терістеу амалы тек қарапайым формулаларға қатысты болса, онда бұл формула нормал формаға ие деп айтады.

Тұжырымдар алгебрасының және предикаттар логикасының тепе-теңдіктерін пайдаланып, предикаттар логикасының кез келген формуласын нормал формаға келтіру мүмкін.

Мысал 1.

формуланы нормал формаға келтірейік.

Тепе-тең түрлендірулерді пайдаланып, келесіні аламыз:

Предикаттар логикасы формулаларының арасында пренекстік (префикстік) нормал форма деп аталатын формулаларды бөліктейді. Бұл формада кванторлық амалдар жоқ болады немесе олар логика алгебрасы барлық амалдарынан кейін қолданылады, яғни предикаттар логикасы формуласының ПНФ келесі түрде болады:

,

мұнда

символы –

немесе

, ал А формуласында кванторлар жоқ.

Теорема. Предикаттар логикасының кез келген формуласын пренекстік нормал формаға келтіру мүмкін.

жүктеу 8,05 Mb.

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

1 ... 40 41 42 43 44 45 46 47 ... 75