На головну

 Висловлювання та операції над ними. | |  Формули алгебри висловлювань. Види формул. |  Вправи. |  вправи |  Равносильность формул алгебри висловлювань. |  вправи |  Нормальні форми для формул алгебри висловлювань. |  Вправи. |  Застосування нормальних форм. |

Знаходження посилок для даних наслідків.

  1.  BDECiientDataSet - клієнтський набір даних.
  2.  Colorspace: - відео рівні даних рівнів
  3.  ER-модель бази даних. Основні нотації зображення ER-моделі.
  4.  II. Основний файл вихідних даних
  5.  II. Основний файл вихідних даних
  6.  III ЕТАП статистичного ДОСЛІДЖЕННЯ - ЕКСПЕРТИЗА ЗВЕДЕННЯ ДАНИХ
  7.  III. Порядок формування даних Звіту

5.37. Знайдіть всі нерівносильні між собою і не тотожне помилкові формули алгебри висловлювань, для яких така формула є логічним наслідком (за винятком самої цієї формули):

а) X «Y;

б) X®Y;

в) XUuY;

г) u (XUY);

д) (XUY) ® (XUY).

Рішення: а) Щоб визначити, логічним наслідком яких посилок є дана формула F (X1, X2, ..., Xn), Її необхідно привести до досконалої кон'юнктивній нормальній формі і потім скласти кон'юнкції формули F з відсутніми в її СКН-формі досконалими диз'юнктивними одночленной виду X * 1U X * 2U ... U X * n (Де X * i Тобто або Xi, Або uXi), Взятими по одному, по два і т. Д.

Наведемо цю формулу до СКН-формі:

X «Y? (X®Y) U (Y®X) ? (uXUY) U (XUuY).

Відсутніми в цій формі диз'юнктивними одночленной виду X * UY * є XUY і uXUuY. Тому шуканими посилками для даної формули є формули (X «Y) U (XUY), (X« Y) U (uXUuY) і (X «Y) U (XUY) U (uXUuY). Перетворимо їх рівносильним чином до більш простими формулами:

(X «Y) U (XUY) ? (uXUY) U (XUuY) U (XUY) ? (uXUY) UX?XUY;

(X «Y) U (uXUuY) ? (uXUY) U (XUuY) U (uXUuY) ? (uXUY) UuY?uXUuY;

(X «Y) U (XUY) U (uXUuY) ? (uXUY) U (XUuY) U (XUY) U (uXUuY) ? (uXUY) U (uXUuY) UX?uXUX?0

(Т. Е. Ця остання посилка є тотожно неправдиву формулу, з якої логічно випливає всяка формула алгебри висловлювань, в тому числі і дана формула X «Y).

Отже, будь-яка формула, для якої формула X «Y є логічним наслідком, рівносильна або формулою XUY, або формулою uXUuY, або тотожне помилкова. Оскільки з тотожно хибною формули логічно випливає будь-яка формула, то ми надалі не будемо згадувати тотожне неправдиву формулу в числі можливих посилок для даної формули (за винятком випадку, коли тотожно помилкова формула є єдиною посилкою для даної формули).

5.38. Знайдіть відсутню посилку (формулу) F, залежить лише від зазначених пропозіціональних змінних так, щоб була вірна наступна виводимість:

а) XUYUZ, uYUV, F (Z, V) | = XUV;

б) X®Z, Y «uV, F (Z, V) | = uXUuY;

в) XUuZ, Y® (XUZ), F (X, Y) | = uYUuZ;

г) X®Z, uYUuZ, Z® (YUV), F (X, Y) | = XUuV;

д) Y®uZ, (XUZ) ® (VUY). F (X, Y) | = X®uV;

е) uXUY, F (X, Y, Z) | = Z.

Рішення: а) Складемо таблиці істинності для формул, які є посилками і висновком:

X Y Z V  XUYU Z  uYUV  XUV  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Далі, в правій колонці відзначимо цифрами ті рядки, в яких обидві дані посилки приймають значення 1, а наслідок приймає значення 0. Цій вимозі відповідає лише четвертий рядок, в якій l (Z) = 1 і l (V) = 1. Ясно, що при цих значеннях Z і V шукана посилка F (Z, V) повинна прийняти значення 0, так як в противному випадку формула XUV НЕ буде логічним наслідком формул XUYUZ, uYUV і F (Z, V) (тому що на значеннях l (X) = 0, l (Y) = 0, l (Z) = 1, l (V) = 1 всі посилки візьмуть значення 1, а формула XUV прийме значення 0). Будемо вважати, що на інших наборах значень змінних Z і V формула F (Z, V) приймає значення 1. Отже, для шуканої посилки F (Z, V) отримуємо наступну таблицю істинності:

Z V  F (Z, V)

Знаходимо СКН-форму для шуканої формули. Отримуємо: F (Z, V) ?uZUuV?Z®uV.

5.39. У наступному міркуванні знайдіть відсутню посилку, яка б пов'язала висловлювання «Прямі a і b лежать в одній площині» і «Прямі a і b схрещуються» так, щоб міркування було правильним:

1) Прямі a і b або паралельні, або перетинаються, або схрещуються.

2) Прямі a і b лежать в одній площині і не перетинаються.

3) ???

Отже, прямі a і b лежать в одній площині і паралельні.

Рішення: Введемо позначення для найпростіших висловлювань, що входять в це міркування:

X: «Прямі a і b паралельні»;

Y: «Прямі a і b перетинаються»;

Z: «Прямі a і b схрещуються»;

V: «Прямі a і b лежать в одній площині».

Тоді задача зводиться до відшукання такої формули F (Z, V), що залежить від змінних Z і V, що справедлива наступна виводимість:

XUYUZ, uYUV, F (Z, V) | = XUV.

У задачі 5.38, а така формула нами знайдена: Z®uV. Залишається надати цій формулі змістовний сенс: «Якщо Прямі a і b схрещуються, то вони не лежать в одній площині».

5.40. У наступному міркуванні знайдіть відсутню посилку так, щоб міркування було правильним і посилка висловлювала зв'язок між висловлюваннями «Ціле число закінчується нулем»; «Ціле число ділиться на 5»; «Ціле число закінчується цифрою 5».

1) Ціле число ділиться на 5 і не закінчується нулем.

2) ???

Отже, ціле число закінчується цифрою 5.

Вказівка: див. Задачу 5.38, е.



 Знаходження наслідків з посилок. |  Булевих функцій (ФУНКЦІЇ АЛГЕБРИ ЛОГІКИ).
© um.co.ua - учбові матеріали та реферати