АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Випереджена нормальна форма

Читайте также:
  1. B) Спортивная форма
  2. B. на процессе сбора, передачи и хранения информации
  3. C) в тексте нет информации
  4. C.) При кодировании текстовой информации в кодах ASCII двоичный код каждого символа в памяти ПК занимает
  5. CASE-технологія створення інформаційних систем
  6. CMS, редактирование информации
  7. D. процессы самоорганизации, информационные процессы и процессы управления в живых системах
  8. g) процесс управления информацией.
  9. I Курс I I семестр (полная форма обучения)
  10. I. ИНФОРМАЦИЯ, КОТОРУЮ НЕОБХОДИМО ЗНАТЬ ДО НАЧАЛА АНКЕТИРОВАНИЯ
  11. II. Формальная логика как первая система методов философии.
  12. III Рондообразная форма.

 

Означення 7.1. Випереджена нормальна форма – формула, записана у вигляді Q1x1Q2x2...QnxnM, де кожне Qixi (i = 1,2,..., n) – це " xi або $ xi, а формула M не містить кванторів. Вираз Q1x1...Qnxn називають префіксом, а M – матрицею формули, записаної у випередженій нормальній формі.

Приклад 7.1. Наведемо приклади формул, записаних у випередженій нормальній формі.

1. " x " y (P (x,y)Ù Q (y)).

2. " x $ y (P (x)Ú Q (y)).

3. " x " y $ z (Q (x,y)Ù R (z)).

4. " x " y " z $ u (P (x,z)Ú P (y,z)Ú Q (x,y,u)). ▲

Для того, щоб перевести формулу у випереджену нормальну форму, необхідно виконати наступні перетворення:

1. Використати правила усунення імплікації (P®Q = Ú Q) та еквівалентності (P~Q =(P®Q)Ù(Q®P)).

2. Застосувати закон подвійного заперечення () та закони де Моргана ().

3. Застосувати закони: Ø(" xP (x))= та Ø($ xP (x))= .

4. Застосувати закони логіки першого ступеня 3-8.

5. Винести квантори у префікс, для чого скористатись законами логіки першого ступеня 3-8.

Приклад 7.2. Зведемо формулу " xP (x)→$ уQ (y) до випередженої нормальної форми за умови, що предикати P (x) і Q (y) не містять вільних змінних. Кроки для побудови випередженої нормальної форми:

1. Вилучення імплікації:

" xP (x)→$ уQ (y)= Ø(" xP (x))Ú$ уQ (y).

2. Застосування закону Ø(" xP (x))= :

Ø(" xP (x))Ú$ уQ (y)= ))Ú$ уQ (y).

3. Винесення квантора існування у префікс:

))Ú$ уQ (y) =$ х $ у ( Ú Q (y)). ▲

Приклад 7.3. Зведемо формулу " x " y ($ zP (x,z)Ù P (y,z))® $ uQ (x,y,u)) до випередженої нормальної форми. Кроки для побудови випередженої нормальної форми:

1. Вилучення імплікації:

" x " y ($ zP (x,z)Ù P (y,z))® $ uQ (x,y,u))= " x " y (Ø($ zP (x,z)Ù P (y,z)))Ú$ uQ (x,y,u)).

2. Застосування закону Ø(" xP (x))= та закону де Моргана:

" x " y (Ø($ zP (x,z)Ù P (y,z)))Ú$ uQ (x,y,u))= " x " y (" z (x,z)Ú (y,z))Ú$ uQ (x,y,u)).

3. Використання законів логіки першого ступеня 6-7 та винесення квантора існування у префікс:

" x " y (" z (x,z)Ú (y,z))Ú$ uQ (x,y,u))= " x " y " z $ u ( (x,z)Ú (y,z)Ú$ uQ (x,y,u)). ▲

 

 


1 | 2 | 3 | 4 | 5 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)