ВАРІАНТ 0. І. Доведіть справедливість рівностіа↔b=(āÚb)Ù(b→а), побудувавши таблицю істинності.

І. Доведіть справедливість рівності а↔ b=(ā Ú b)Ù (b→ а), побудувавши таблицю істинності.

РОЗВ ’ ЯЗАННЯ:

Таблиця складатиметься із семи стовпців (а, b, а↔ b, ā, ā Ú b, b→ а, (ā Ú b)Ù (b→ а)), а число рядків визначається за формулою 2ⁿ+1, де n – кількість елементарних висловлень, що входять у вираз, і дорівнює 2²+1=5. Щоб заповнити перші два стовпця, перебираємо всі можливі варіанти значень істинності висловлень а і b. Для заповнення третього стовпця виконаємо заперечення значень першого стовпця. Заповнюючи четвертий стовпець, виконуємо імплікацію першого стовпця в другий. П’ятий стовпець являє собою диз’юнкцію значень другого і третього стовпців. Для заповнення шостого стовпця виконуємо імплікацію значень другого стовпця у перший. І нарешті, для заповнення сьомого стовпця виконаємо кон’юнкцію п’ятого і шостого стовпців.

Значення лівої частини рівності при всіх наборах значень істинності висловлень, які входять до лівої частини представлені у четвертому стовпці, а значення правої частини – у сьомому стовпці. Порівнюючи їхні значення, бачимо, що вони співпадають, а тому справедливість рівності а↔ b=(ā Ú b)Ù (b→ а) доведена.

ІІ. Спростити вираз: a→ bÚ cÙ aÚ bÚ c→ (aÚ b)Ù b→ c.

РОЗВ ’ ЯЗАННЯ:

Спочатку використаємо формулу a→ b=aÚ b, а тому одержимо:

aÚ bÚ cÙ aÚ bÚ cÚ (aÚ b)Ù bÚ c=

Використовуючи закони де Моргана (aÚ b=aÙ b чи aÙ b=aÚ b), маємо:

=aÚ bÚ cÙ aÙ bÙ cÙ aÙ bÚ bÚ c=

Використавши закон подвійного заперечення (а=а), маємо:

=aÚ bÚ cÙ aÙ bÙ cÙ aÙ bÚ bÚ c=

Використовуючи закони ідемпотентності (аÚ а=а, аÙ а=а), маємо:

=aÚ bÚ cÙ aÙ bÙ bÚ bÚ c=

Оскільки bÙ b=0 і аÙ 0=0, то маємо:

aÚ bÚ cÙ aÙ 0Ú bÚ c=aÚ bÚ cÙ 0Ú bÚ с=aÚ bÚ 0Ú bÚ с= aÚ bÚ bÚ с= aÚ 1Ú с=1.

ІІІ. Перетворіть у висловлення заданий предикат А(х): «сума цифр натурального числа х ділиться націло на 12», застосувавши спочатку квантор існування, а потім квантор загальності, та визначіть істинність одержаних висловлень.

РОЗВ ’ ЯЗАННЯ:

Застосувавши спочатку квантор існування, одержимо висловлення ($хєN)А(х): «існує таке натуральне число х, яке ділиться націло на 12». Це висловлення істинне, бо дійсно серед натуральних чисел існують числа, що діляться націло на 12, наприклад: 12, 24, 36 та ін.

Якщо застосуємо квантор загальності, то одержимо висловлення (" хєN)А(х): «Всяке натуральне число х ділиться націло на 12». Це висловлення буде хибним, бо серед натуральних чисел є такі, які не діляться націло на 12, наприклад: 1, 2, 3, 45 та ін.

ІУ. З’ясувати у якому із відношень (логічного слідування чи рівносильності знаходяться задані предикати А(х): «дві останні цифри у записі натурального числа х утворюють числа 25 або 75» і В(х): «натуральне число х ділиться націло на 25».

РОЗВ ’ ЯЗАННЯ:

Згідно означення предикат А(х) логічно випливає із предиката В(х), якщо вони задані на одній множині та коли Т_АÌ Т_В. Отже, щоб визначити чи випливає логічно предикат А(х) із предиката В(х) потрібно дотримуватися такого алгоритму: 1) з’ясувати, чи на одній множині задані обидва предикати; 2) знайти множини істинності кожного з предикатів; 3) виявити співвідношення між множинами істинності предикатів; 4) якщо одна з множин істинності є підмножиною іншої, то зробити висновок про відношення логічного слідування між предикатами. Легко переконатися, що обидва предикати А(х) і В(х) задані на одній і тій самій множині натуральних чисел. Знайдемо множину істинності предиката А(х). Т_А={25, 75, 125, 175, 225, 275, …}. Множиною істинності предиката В(х) буде наступна множина Т_B={25, 50, 75, 100, 125, 150, 175, 200, 225, 250, 275, 300, …}. Легко бачити, що справедливе твердження Т_АÌ Т_В. Отже, предикат А(х) логічно випливає із предиката В(х), тобто: А(х)╞ В(х).

Якщо використати друге означення: «якщо імплікація А(х)→ В(х)=1 при всіх хєХ, то говорять, що предикат В(х) логічно слідує з предиката А(х)», то слід утворити імплікацію А(х)→ В(х) та зясувати значення її істинності. А(х)→ В(х): «якщо дві останні цифри у записі натурального числа х утворюють числа 25 або 75, то натуральне число х ділиться націло на 25». Ця імплікація істинна, а тому А(х)╞ В(х).

Розглянемо два предикати: А(х): «запис натурального числа х закінчується цифрами 00, 25, 50, 75» і В(х): «натуральне число х ділиться націло на 25» та зясуємо чи знаходяться вони у відношенні рівносильності. Як відомо, два предикати А(х) і В(х), які задані на множині Х, називаються рівносильними, якщо еквіваленція цих предикатів А(х)↔ В(х) істинна при всіх хєХ. Щоб перевірити, чи рівносильні предикати слід з’ясувати наступне: 1) чи задані предикати на одній множині; 2) утворити еквіваленцію заданих простих предикатів; 3) знайти множину істинності еквіваленції; 4) порівняти область визначення та множину істинності; 5) якщо вони співпадають, то зробити висновок про те, що предикати знаходяться у відношенні рівносильності.

Обидва предикати задані на множині натуральних чисел, тобто на одній і тій самій множині. Утворимо еквіваленцію заданих предикатів: А(х)↔ В(х): «натуральне число х тоді і тільки тоді ділиться на 25, коли запис натурального числа х закінчується цифрами 00, 25, 50, 75». Легко визначити, що ця еквіваленція істинна для натуральних чисел, для яких виконується вказана умова. Отже, задані предикати рівносильні, тобто А(х)≡ В(х).

У. Записати теорему «Якщо діагоналі прямокутника перпендикулярні, то цей прямокутник - квадрат» символічно з використанням кванторів, утворити три спряжені з нею, вказати їх множину істинності, вказати роз’яснюючу частину, умову та висновок.

РОЗВ ’ ЯЗАННЯ:

Кожна теорема має своїми структурними елементами роз’яснюючу частину, яка, як правило, задається квантором існування чи загальності, умову і висновок, які задаються предикатами. Будь-яку теорему можна записати в імплікативній формі: ($хєХ)[А(х)→ В(х)] чи (" хєХ)[А(х)→ В(х)], де ($хєХ) чи (" хєХ) – роз’яснююча частина, А(х) – умова теореми, В(х) – висновок теореми. Запишемо теорему «Якщо діагоналі прямокутника перпендикулярні, то цей прямокутник - квадрат» у символічній формі, врахувавши, що область визначення Х - це множина всіх прямокутників, а теорема стосується всіх прямокутників, а тому слід застосувати квантор загальності. Отже, роз’яснююча частина у символічний формі запишеться так: (" хєХ). Цей символічний запис стосовно даної теореми слід так: для будь-якого прямокутника. Умова теореми являє собою предикат А(х): «діагоналі прямокутника Х - перпендикулярні». Висновок теореми є предикатом В(х): «прямокутник Х - квадрат». Таким чином, задана теорема у символічній формі запишеться так: (" хєХ)[А(х)→ В(х)]: «якщо діагоналі будь-якого прямокутника перпендикулярні, то цей прямокутник - квадрат». Це висловлення істинне, а тому дана теорема є справедливою.

Відомо, що кожна теорема має три спряжені: 1) теорема, обернена до даної. Щоб отримати її, слід поміняти місцями умову і висновок даної теореми. Обернена теорема запишеться так: (" хєХ)[В(х)→ А(х)]: «якщо будь-який прямокутник – квадрат, то його діагоналі перпендикулярні». Ця теорема також істинна, тобто В(х)→ А(х)=1 для всіх хєХ. 2) теорема, протилежна до даної. Для того щоб її одержати, необхідно заперечити умову і висновок даної теореми. Протилежна до даної теорема запишеться так: (" хєХ)[А(х)→ В(х)]: «якщо діагоналі будь-якого прямокутника не перпендикулярні, то цей прямокутник - не квадрат». Ця теорема також істинна, тобто А(х)→ В(х)=1 для всіх хєХ. 3) теорема, обернена до протилежної чи протилежна до оберненої. Для того, щоб її записати слід поміняти місцями умову і висновок в протилежній до даної теоремі або заперечити умову і висновок в теоремі, оберненій до даної. Таким чином, теорема, обернена до протилежної чи протилежна до оберненої запишеться так: (" хєХ)[В(х)→ А(х)]: «якщо будь-який прямокутник – не квадрат, то його діагоналі не перпендикулярні». Ця теорема істинна, тобто: В(х)→ А(х)=1 для всіх хєХ.

Оскільки всі чотири теореми істинні. То їх можна замінити однією, використовуючи слова необхідно і достатньо, а саме: для того, щоб прямокутник був квадратом, необхідно і достатньо, щоб його діагоналі були взаємно перпендикулярними.

УІ. З’ясувати, чи є дана умова M→ K=«якщо ху=0, то у=0» необхідною, достатньою, чи необхідною і достатньою?

РОЗВ ’ ЯЗАННЯ:

Відповідно до означення, якщо імплікація M→ K істинна, тобто M→ K=1, то предикат К(х) називається необхідною умовою для предиката М(х), а предикат М(х) достатньою умовою для предиката К(х). Якщо ж істинні обидві імплікації M→ K і K→ M, тобто M→ K=1 і K→ M=1, то предикат К(х) називають необхідною і достатньою умовою для предиката М(х).

Якщо ху=0, то не обов’язково, щоб у=0, бо при х=0 і у≠ 0 маємо ху=0. Отже, імплікація M→ K хибна, а тому предикат К(х) не буде необхідною умовою для предиката М(х).

Якщо у=0, то ху=0. Отже, імплікація K→ M істинна, а тому предикат М(х) є необхідною умовою для предиката К(х). Окрім того, предикат К(х) є достатньою умовою для предиката М(х).