Розділ 2: Повні таблиці істинності

Last updated
Save as PDF

Page ID: 52217

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

Істинне значення речень, які містять лише один сполучний, задаються характерною таблицею істинності для цього сполучного. У попередньому розділі ми написали характерні таблиці істинності з 'T' для true і 'F' для false. Однак важливо зазначити, що мова йде не про істину в якомусь глибокому чи космічному сенсі. Поети та філософи можуть довго сперечатися про природу та істотну істину, але функції істини в SL - це лише правила, які перетворюють вхідні значення у вихідні значення. Щоб підкреслити це, у цьому розділі ми напишемо '1' і '0' замість 'T' і 'F '. Незважаючи на те, що ми інтерпретуємо «1» як значення «правда» і «0» як значення «брехня», комп'ютери можуть бути запрограмовані на заповнення таблиць правди чисто механічним способом. У машині «1» може означати, що регістр увімкнено, а «0», що регістр перемикається o. Математично вони є лише двома можливими значеннями, які може мати речення SL.

Ось таблиці істинності для з'єднань SL, написані термінами 1s і 0s.

\(\mathcal{A}\)

¬\(\mathcal{A}\)

\(\mathcal{A}\)

\(\mathcal{B}\)

\(\mathcal{A}\)&\(\mathcal{B}\)

\(\mathcal{A}\)∨\(\mathcal{B}\)

\(\mathcal{A}\)→\(\mathcal{B}\)

\(\mathcal{A}\)↔\(\mathcal{B}\)

Таблиця 3.1: Характеристичні таблиці істинності для з'єднань SL.

Характерна таблиця істинності для сполучника, наприклад, дає умови істинності для будь-якого речення виду (\(\mathcal{A}\)&\(\mathcal{B}\)). Навіть якщо сполучники\(\mathcal{A}\) і\(\mathcal{B}\) є довгими, складними реченнями, сполучник істинний тоді і тільки тоді, коли обидва\(\mathcal{A}\) і\(\mathcal{B}\) є істинними. Розглянемо речення (\(H\)&\(I\)) →\(H\). Розглянемо всі можливі комбінації true і false для\(H\) і\(I\), що дає нам чотири ряди. Потім ми копіюємо істинні значення для букв речення і записуємо їх під літерами в реченні.

\(H\)

\(I\)

(\(H\)&\(I\)) →\(H\)

1 1 1

1 0 1

0 1 0

0 0 0

Тепер розглянемо підречення\(H\) &\(I\). Це сполучення\(\mathcal{A}\) &\(\mathcal{B}\) з\(H\) як\(\mathcal{A}\) і з\(I\) як\(\mathcal{B}\). \(H\)і\(I\) обидва вірні в першому рядку. Оскільки кон'юнкція істинна, коли обидва кон'юнкти є істинними, ми пишемо 1 під символом сполучника. Продовжуємо для інших трьох рядів і отримуємо ось що:

\(H\)

\(I\)

(\(H\)&\(I\)) →\(H\)

\(\mathcal{A}\)&\(\mathcal{B}\)

1 1 1 1

1 0 0 1

0 0 1 0

0 0 0 0

Усе речення є\(\mathcal{B}\) умовним\(\mathcal{A}\) → з (\(H\)&\(I\)) як\(\mathcal{A}\) і з\(H\) as\(B\). У другому рядку, наприклад, (\(H\)&\(I\)) є false і\(H\) є true. Оскільки умова істинна, коли попередник є помилковим, ми запишемо 1 у другому рядку під умовним символом. Продовжуємо для інших трьох рядів і отримуємо ось що:

\(H\)

\(I\)

(\(H\)&\(I\)) →\(H\)

\(\mathcal{A}\)→\(\mathcal{B}\)

1 1 1

0 1 1

0 1 0

Стовпець 1s під умовним повідомляє нам, що речення (\(H\)&\(I\)) →\(I\) є істинним незалежно від істинних значень\(H\) і\(I\). Вони можуть бути істинними або помилковими в будь-якому поєднанні, а складне речення все одно виходить істинним. Дуже важливо, щоб ми розглянули всі можливі комбінації. Якби у нас була лише дворядкова таблиця істинності, ми не могли бути впевнені, що речення не є помилковим для якоїсь іншої комбінації істинних значень.

У цьому прикладі ми не повторювали всі записи в кожній послідовній таблиці. Однак при написанні таблиць правди на папері недоцільно стирати цілі стовпці або переписувати всю таблицю для кожного кроку. Хоча це більш людно, таблицю істинності можна записати таким чином:

\(H\)

\(I\)

(\(H\)&\(I\)) →\(H\)

\(\mathcal{A}\)→\(\mathcal{B}\)

1 1 1 1 1

1 0 0 1 1

0 0 1 1 0

0 0 0 1 0

Більшість стовпців під реченням є лише для цілей бухгалтерського обліку. Коли ви станете більш досвідченими з таблицями істини, вам, ймовірно, більше не потрібно буде копіювати стовпці для кожної з букв речення. У будь-якому випадку, істинне значення речення у кожному рядку - це лише стовпець під основним логічним оператором речення; у цьому випадку стовпець під умовним.

Повна таблиця істинності містить рядок для всіх можливих комбінацій 1 і 0 для всіх букв пропозиції. Розмір повної таблиці істинності залежить від кількості різних букв пропозиції в таблиці. Речення, що містить тільки одну букву пропозиції, вимагає всього двох рядків, як в характерній таблиці істинності для заперечення. Це вірно, навіть якщо одна і та ж буква повторюється багато разів, як у реченні [(\(C\)↔\(C\)) →\(C\)] &¬ (\(C\)→\(C\)). Повна таблиця істинності вимагає лише двох рядків, оскільки існує лише дві можливості:\(C\) може бути істинною або помилковою. Одна буква речення ніколи не може бути позначена як 1, так і 0 в одному рядку. Таблиця істинності для цього речення виглядає наступним чином:

\(C\)

[(\(C\)↔\(C\)) →\(C\)] & ¬ (\(C\)→\(C\))

1 1 1 1 1 0 1 1

0 1 0 0 0 0 0 0 1 0

Дивлячись на стовпець під основним сполучним, ми бачимо, що речення помилкове на обох рядках таблиці; тобто воно помилкове незалежно від того,\(C\) правда чи хибно.

Речення, яке містить дві літери речення, вимагає чотирьох рядків для повної таблиці істинності, як у характерних таблицях істинності та таблиці для (\(H\)&\(I\)) →\(I\).

Речення, яке містить три літери речення, вимагає восьми рядків. Наприклад:

\(M\)

\(N\)

\(P\)

\(M\)& (\(N\)∨\(P\))

1 1 1 1 1

1 1 1 1 0

1 1 0 1

1 0 0 0 0

0 0 1 1

0 0 1 1 0

0 0 0 1 1

0 0 0 0

З цієї таблиці ми знаємо, що речення\(M\) & (\(N\)∨\(P\)) може бути істинним або хибним, залежно від істинних значень\(M\)\(N\), і\(P\).

Повна таблиця істинності для речення, що містить чотири різні літери речення, вимагає 16 рядків. П'ять букв, 32 рядки. Шість букв, 64 рядки. І так далі. Щоб бути абсолютно загальним: Якщо повна таблиця істинності має\(\mathcal{n}\) різні літери пропозицій, то вона повинна мати 2 ⁿ рядків.

Для того, щоб заповнити стовпці повної таблиці істинності, почніть з крайньої правої літери речення і чергуйте 1s і 0s. У наступному стовпці зліва напишіть два 1s, напишіть два 0s, і повторіть. Для третього листа пропозиції напишіть чотири 1s, а потім чотири 0s. Це дає вісім рядків таблиці істинності, як і вище. Для 16-рядкової таблиці істинності наступний стовпець букв речення повинен мати вісім 1s, а потім вісім 0s. Для таблиці рядків 32 наступний стовпець матиме 16 1s, а потім 16 0s. І так далі.