Мои Конспекты
Главная | Обратная связь


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

Хід заняття



 

Задача 1. Привести приклади рівносильних елементарних кон’юнкцій (диз'юнкцій), але не рівних.

Задача 2.Рівносильними перетвореннями приведіть формулу до диз‘юнктивної нормальної форми:

Ø(XÚZ)Ù(X®Y)

 

Розв’язування.

Ø(XÚZ)Ù(X®Y) =

Закон де Моргана для диз'юнкцiї (10°)

(ØXÙØZ)Ù(X®Y) =

Вираження iмплiкацiї через диз'юнкцiю та заперечення (21°)

(ØXÙØZ)Ù(ØXÚY) =

Закон дистрибутивностi кон'юнкцiї вiдносно диз'юнкцiї (7°)

((ØXÙØZ)ÙØX)Ú((ØXÙØZ)ÙY) =

Закон комутативностi кон'юнкцiї (2°)

(ØXÙ(ØXÙØZ))Ú((ØXÙØZ)ÙY) =

Закон асоцiативностi кон'юнкцiї (5°)

((ØXÙØX)ÙØZ)Ú((ØXÙØZ)ÙY) =

Закон iдемпотентностi кон'юнкцiї (12°)

(ØXÙØZ)Ú (ØXÙØZÙY)

Дана формула має наступну ДН-форму:

(ØXÙØZ)Ú(ØXÙYÙØZ)

 

Задача 3. Рівносильними перетвореннями приведіть формулу до кон‘юнктивної нормальної форми:

(X«Y)ÙØ(Z®T)

 

Розв’язування.

(X«Y)ÙØ(Z®T) =

Вираження еквiваленцiї через iмплiкацiю та кон'юнкцiю (25°)

(X®Y)Ù(Y®X)ÙØ(Z®T) =

Вираження iмплiкацiї через диз'юнкцiю та заперечення (21°)

(ØXÚY)Ù(Y®X)Ù Ø(Z®T) =

Вираження iмплiкацiї через диз'юнкцiю та заперечення (21°)

(ØXÚY)Ù(ØYÚX)ÙØ(Z®T) =

Вираження iмплiкацiї через диз'юнкцiю та заперечення (21°)

(ØXÚY)Ù(ØYÚX)ÙØ(ØZÚT) =

Закон де Моргана для диз'юнкцiї (10°)

(ØXÚY)Ù(ØYÚX)ÙØØZÙØT =

Закон подвiйного заперечення (1°)

(ØXÚY)Ù(ØYÚX)ÙZÙØT

Дана формула має наступну КН-форму:

(ØXÚY)Ù(XÚØY)ÙZÙØT

Задача 4. Рівносильними перетвореннями приведіть формулу до досконалої диз‘юнктивної нормальної форми:

XÚ(YÙZ)

 

Розв’язування.

Кон’юнктивний одночлен Y Ù Z не є досконалим вiд трьох змiнних X,Y i Z, так як до нього не входить змiнна X. Введення змiнної X робиться наступним чином:

XÚ(YÙZ) =

Закон одиницi вiдносно кон'юнкцiї (13°)

XÚ((YÙZ)Ù1) =

Вираження одиницi через диз'юнкцiю та заперечення (18°)

XÚ((YÙZ)Ù(XÚØX)) =

Закон дистрибутивностi кон'юнкцiї вiдносно диз'юнкцiї (7°)

XÚ((YÙZ)ÙX)Ú((YÙZ)ÙØX) =

В одночленi X не вистачає двох змiнних Y i Z. Введемо спочатку змiнну Y:

Закон одиницi вiдносно кон'юнкцiї (13°)

(XÙ1)Ú((YÙZ)ÙX)Ú((YÙZ)ÙØX) =

Вираження одиницi через диз'юнкцiю та заперечення (18°)

(XÙ(YÚØY))Ú((YÙZ)ÙX)Ú((YÙZ) ÙØX) =

Закон дистрибутивностi кон'юнкцiї вiдносно диз'юнкцiї (7°)

(XÙY)Ú(XÙØY)Ú((YÙZ)ÙX)Ú((YÙZ)ÙØX) =

В одночленi X ÙØY не вистачає змiнної Z. Введемо змiнну Z:

Закон одиницi вiдносно кон'юнкцiї (13°)

(XÙY)Ú((XÙØY)Ù1)Ú((YÙZ)ÙX)Ú((YÙZ)ÙØX) =

Вираження одиницi через диз'юнкцiю та заперечення (18°)

(XÙY)Ú((XÙØY)Ù(ZÚØZ))Ú((YÙZ)ÙX)Ú((YÙZ)ÙØX) =

Закон дистрибутивностi кон'юнкцiї вiдносно диз'юнкцiї (7°)

(XÙY)Ú((XÙØY)ÙZ)Ú((XÙØY)ÙØZ)Ú((YÙZ)ÙX)Ú((YÙZ)ÙØX) =

В одночленi X Ù Y не вистачає змiнної Z. Введемо змiнну Z:

Закон одиницi вiдносно кон'юнкцiї (13°)

((XÙY)Ù1)Ú((XÙØY)ÙZ)Ú((XÙØY)ÙØZ)Ú((YÙZ)ÙX)Ú((YÙZ)ÙØX) =

Вираження одиницi через диз'юнкцiю та заперечення (18°)

((XÙY)Ù(ZÚØZ))Ú((XÙØY)ÙZ)Ú((XÙØY)ÙØZ)Ú((YÙZ)ÙX)Ú((YÙZ)ÙØX) =

Закон дистрибутивностi кон'юнкцiї вiдносно диз'юнкцiї (7°)

((XÙY)ÙZ)Ú((XÙY)ÙØZ)Ú((XÙØY)ÙZ)Ú((XÙØY)ÙØZ)Ú((YÙZ)ÙX)Ú((YÙZ)ÙØX) =

Закон комутативностi кон'юнкцiї (2°)

((XÙY)ÙZ)Ú((XÙY)ÙØZ)Ú((XÙØY)ÙZ)Ú((XÙØY)ÙØZ)Ú(XÙ(YÙZ))Ú((YÙZ)ÙØX) =

Закон iдемпотентностi диз'юнкцiї (11°)

((XÙY)ÙZ)Ú((XÙY)ÙØZ)Ú((XÙØY)ÙZ)Ú((XÙØY)ÙØZ)Ú((YÙZ)ÙØX) =

Закон комутативностi кон'юнкцiї (2°)

((XÙY)ÙZ)Ú((XÙY)ÙØZ)Ú((XÙØY)ÙZ)Ú((XÙØY)ÙØZ)Ú(ØXÙ(YÙZ))

Дана формула має наступну ДДН-форму:

(XÙYÙZ)Ú(XÙYÙØZ)Ú(XÙØYÙZ)Ú(XÙØYÙØZ)Ú( ØX ÙYÙZ)

Задача 5. Рівносильними перетвореннями приведіть формулу до досконалої кон‘юнктивної нормальної форми:

(XÚY)ÙZ

 

Розв’язування.

Диз’юнктивний одночлен X Ú Y не є досконалим вiд трьох змiнних X,Y i Z, так як до нього не входить змiнна Z. Введення змiнної Z робиться наступним чином:

(XÚY)ÙZ =

Закон нуля вiдносно диз'юнкцiї (14°)

(XÚYÚ0)ÚZ =

Вираження нуля через кон'юнкцiю та заперечення (15°)

(XÚYÚ(ZÚØZ))ÚZ =

Закон дистрибутивностi диз'юнкцiї вiдносно кон'юнкцiї (8°)

(XÚ(YÚZ)Ú(YÚØZ))ÚZ =

Закон дистрибутивностi диз'юнкцiї вiдносно кон'юнкцiї (8°)

(XÚYÚZ)Ú(XÚYÚØZ)ÚZ =

В одночленi Z не вистачає двох змiнних X i Y. Введемо спочатку змiнну X:

Закон нуля вiдносно диз'юнкцiї (14°)

(XÚYÚZ)Ú(XÚYÚØZ)Ú(ZÚ0) =

Вираження нуля через кон'юнкцiю та заперечення (15°)

(XÚYÚZ)Ú(XÚYÚØZ)Ú(ZÚXÚØX) =

Закон дистрибутивностi диз'юнкцiї вiдносно кон'юнкцiї (8°)

(XÚYÚZ)Ú(XÚYÚØZ)Ú(ZÚX)Ú(ZÚØX) =

В одночленi Z Ú X не вистачає змiнної Y. Введемо змiнну Y:

Закон нуля вiдносно диз'юнкцiї (14°)

(XÚYÚZ)Ú(XÚYÚØZ)Ú(ZÚXÚ0)Ú(ZÚØX) =

Вираження нуля через кон'юнкцiю та заперечення (15°)

(XÚYÚZ)Ú(XÚYÚØZ)Ú(ZÚXÚYÚØY)Ú(ZÚØX) =

Закон дистрибутивностi диз'юнкцiї вiдносно кон'юнкцiї (8°)

(XÚYÚZ)Ú(XÚYÚØZ)Ú(ZÚ(XÚY)Ú(XÚØY))Ú(ZÚØX) =

Закон дистрибутивностi диз'юнкцiї вiдносно кон'юнкцiї (8°)

(XÚYÚZ)Ú(XÚYÚØZ)Ú(ZÚXÚY)Ù(ZÚXÚØY)Ù(ZÚØX) =

В одночленi Z Ú ØX не вистачає змiнної Y. Введемо змiнну Y:

Закон нуля вiдносно диз'юнкцiї (14°)

(XÚYÚZ)Ú(XÚYÚØZ)Ú(ZÚXÚY)Ú(ZÚXÚØY)Ú(ZÚØXÚ0) =

Вираження нуля через кон'юнкцiю та заперечення (15°)

(XÚYÚZ)Ú(XÚYÚØZ)Ú(ZÚXÚY)Ú(ZÚXÚØY)Ú(ZÚØXÚYÚØY) =

Закон дистрибутивностi диз'юнкцiї вiдносно кон'юнкцiї (8°)

(XÚYÚZ)Ú(XÚYÚØZ)Ú(ZÚXÚY)Ú(ZÚXÚØY)Ú(ZÚ(ØXÚY)Ú(ØXÚØY)) =

Закон дистрибутивностi диз'юнкцiї вiдносно кон'юнкцiї (8°)

(XÚYÚZ)Ú(XÚYÚØZ)Ú(XÚYÚZ)Ú(XÚØYÚZ)Ú(ØXÚYÚZ)Ú(ØXÚØYÚZ) =

Закон iдемпотентностi кон'юнкцiї (12°)

(XÚYÚZ)Ú(XÚYÚØZ)Ú(XÚØYÚZ)Ú(ØXÚYÚZ)Ú(ØXÚØYÚZ)

Дана формула має наступну ДКН-форму:

(XÚYÚZ)Ú(XÚYÚØZ)Ú(XÚØYÚZ)Ú(ØXÚYÚZ)Ú(ØXÚØYÚZ)

 

Задача 6. Використовуючи ДДН-форму, знайдіть формулу, що приймає значення 1 на наступних наборах значень змінних, і тільки на них:

F(0,1,0)=F(1,0,1)= F(1,1,1)=1

 

Розв’язування.

Вiзьмемо першу умову F(0,1,0)=1. Оскiльки кон’юнктивний одночлен XÙYÙZ приймає значення 1 тодi i тiльки тодi, коли X =1, Y=1, Z=1, то кон’юнкцiя XÙYÙZ приймає значення 1 тодi i тiльки тодi, коли X=1, Y=1, Z=1, тому X =0, Y=1, Z=0.

Першiй умовi задовольняє лише кон’юнктивний одночлен XÙYÙZ, другiй XÙYÙZ, третiй XÙYÙZ. Тодi формула

F(X, Y, Z) = (XÙYÙZ) Ú (XÙYÙZ) Ú (XÙYÙZ) приймає значення 1, тодi i тiльки тодi, коли XÙYÙZ приймає значення 1, або XÙYÙZ приймає значення 1, або XÙYÙZ приймає значення 1,тобто якщо i тiльки якщо (X, Y, Z) = (0,1,0) або (X, Y, Z) = (1,0,1), або (X, Y, Z) = (1,1,1).

Тодi, F(X, Y, Z) – знайдена формула.

Задача 7. Використовуючи ДКН-форму, знайдіть формулу, що приймає значення 0 на наступних наборах значень змінних, і тільки на них:

F(0,1,1)=F(0,0,0)= F(0,1,0)=0

 

Розв’язування.

Вiзьмемo першу умову F(0,1,1)=0. Оскiльки диз’юнктивний одночлен XÚYÚZ приймає значення 0 тодi i тiльки тодi, коли X=0, Y=0, Z=0, то диз’юнкцiя XÚYÚZ приймає значення 0 тодi i тiльки тодi, коли X=0, Y=0, Z=0 тому X=0, Y=1, Z=1.

Першiй умовi задовольняє лише диз’юнктивний одночлен XÚYÚZ, другiй XÚYÚZ, третiй XÚYÚZ. Тодi формула

F(X, Y, Z) = (XÚYÚZ) Ù (XÚYÚZ) Ù (XÚYÚZ) приймає значення 0, тодi i тiльки тодi, коли XÚYÚZ приймає значення 0, або XÚYÚZ приймає значення 0, або XÚYÚZ приймає значення 0, тобто якщо i тiльки якщо (X, Y, Z) = (0,1,1), або (X, Y, Z) = (0,0,0), або (X, Y, Z) = (0,1,0).

Тодi, F(X, Y, Z) – знайдена формула.

Задача 8.Для даної формули алгебри висловлень знайдіть ДДН-форму за допомогою її таблиці істинності:

Ø(XÙY)®Ø(XÚZ)

 

Розв’язування.

Складемо таблицю iстинностi даної формули:

Вибираючи набори значень змiнних, на яких формула приймає значення 1, так як це робили в задачi 6, записуємо досконалу диз’юнктивну нормальну форму для даної формули:

(XÙY)®(XÚZ) º (XÙYÙZ) Ú (XÙYÙZ) Ú (XÙYÙZ) Ú (XÙYÙZ).

Задача 9.Для даної формули алгебри висловлень знайдіть ДКН-форму за допомогою її таблиці істинності:

Ø(XÙY)®Ø(XÚZ)

Розв’язування.

Складемо таблицю iстинностi даної формули:

Вибираючи набори значень змiнних, на яких формула приймає значення 0, так як це робили в задачi 7, записуємо досконалу кон’юнктивну нормальну форму для даної формули:

(XÙY)®(XÚY) º (XÚYÚZ) Ù (XÚYÚZ) Ù (XÚYÚZ) Ù (XÚYÚZ).