Хід заняття

Задача 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).

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