logo

TechCodeview

Импликация в дискретната математика

Изявление за импликация може да бъде представено във формата „ако...тогава“. Символът ⇒ се използва за показване на импликацията. Да предположим, че има две твърдения, P и Q. В този случай твърдението „ако P тогава Q“ може също да бъде записано като P ⇒ Q или P → Q и ще се чете като „P предполага Q“. В тази импликация твърдението P е хипотеза, която също е известна като предпоставка и предшестващо, а твърдението Q е заключение, което също е известно като следствие.

Импликацията също играе важна роля в логическия аргумент. Ако се знае, че импликацията на твърденията е вярна, тогава когато предпоставката е изпълнена, заключението също трябва да е вярно. Поради тази причина импликацията е известна също като условно твърдение.

Някои примери за последици са описани по-долу:

kmp алгоритъм
  • „Ако времето в GOA е слънчево, тогава ще отидем на плаж“.
  • „Ако клубът има система за отстъпки, тогава ще отидем при този клуб“.
  • „Ако е слънчево, докато отиваме на плаж, тогава ще сме загорели“.

Логическата импликация може да бъде изразена по различни начини, които са описани по следния начин:

  1. Ако p, тогава q
  2. Ако p, q
  3. q когато p
  4. Q само ако P
  5. q освен ако ~p
  6. q винаги, когато p
  7. p е достатъчно условие за q
  8. q следвайте p
  9. p предполага q
  10. Необходимо условие за p е q
  11. q ако p
  12. q е необходимо за p
  13. p е необходимо условие за q

Сега ще опишем примерите за всички гореописани импликации с помощта на предпоставка P и заключение Q. За това ще приемем, че P = Слънчево е и Q = Ще отида на плажа.

P ⇒ Q

  1. АКО е слънчево, тогава ще отида на плаж
  2. АКО е слънчево, ще отида на плаж
  3. Ще отида на плаж, КОГАТО е слънчево
  4. Ще ходя на плаж САМО АКО е слънчево
  5. Ще отида на плаж, ОСВЕН АКО не е слънчево
  6. Ще ходя на плаж ВСЕКИ КОГАТО е слънчево
  7. Слънчево е ДОСТАТЪЧНО УСЛОВИЕ, ЗА ЩЕ ИДАМ НА ПЛЪЖ
  8. Ще отида до плажа СЛЕДВАЙ, слънчево е
  9. Слънчево е ЗНАЧИ, че ще отида на плаж
  10. НЕОБХОДИМО УСЛОВИЕ ЗА да е слънчево е ще ходя на плаж
  11. Ще отида на плаж, АКО е слънчево
  12. Ще отида на плаж Е НЕОБХОДИМО, ЗАЩОТО е слънчево
  13. Слънчево Е НЕОБХОДИМО УСЛОВИЕ ЗА Ще ходя на плаж

Когато има условно твърдение „ако p, тогава q“, тогава това твърдение P ⇒ Q ще бъде невярно, когато Предпоставки p е вярно, а Заключение q е невярно. Във всички останали случаи това означава, че когато p е невярно или Q е вярно, твърдението P ⇒ Q ще бъде вярно. Можем да представим това твърдение с помощта на таблица на истината, в която невярното ще бъде представено от F, а истината ще бъде представено от T. Таблицата на истината на твърдението „ако P, тогава Q“ е описана по следния начин:

П Q P ⇒ q
T T T
T Е Е
Е T T
Е Е T

Не е необходимо предпоставките и заключението да са свързани помежду си. Въз основа на формулировката на P и Q, интерпретацията на таблицата на истината е зависима.

Например:

  • Ако Джак е направен от пластмаса, тогава Океанът е зелен.
  • Твърдението: Джакът е изработен от пластмаса
  • Твърдението: Океанът е зелен

Горните две твърдения нямат никакъв смисъл, защото Джак е човек и никога не може да бъде направен от пластмаса, а друго твърдение Океанът е зелен никога няма да се случи, защото океанът винаги е син и цветът на Океан не може да бъде променен. Както виждаме, двете твърдения не са свързани едно с друго. От друга страна, таблицата на истинност за твърдението P ⇒ Q е валидна. Така че не става въпрос дали таблицата на истината е правилна или не, а е въпрос на въображение и интерпретация.

Така че в P ⇒ Q не се нуждаем от никакъв вид връзка между предпоставката и следствието. Въз основа на истинската стойност на P и Q зависи само значението на тях.

Тези твърдения също ще бъдат неверни, дори ако разгледаме и двете твърдения за нашия свят, така че

 False ⇒ False

Така че, когато погледнем горната таблица на истината, виждаме, че когато P е невярно и Q е невярно, тогава P ⇒ Q е вярно.

Така че, ако Джакът е направен от пластмаса, тогава Океанът ще бъде зелен.

Предпоставка p и заключение q обаче ще бъдат свързани и двете твърдения имат смисъл.

Неяснота

Може да има неяснота в подразбиращия се оператор. Така че, когато използваме оператора за подразбиране (⇒), в този момент трябва да използваме скобите.

Например: В този пример имаме двусмислено твърдение P ⇒ Q ⇒ R. Сега имаме две двусмислени твърдения ((P ⇒ Q) ⇒ R) или (P ⇒ (Q ⇒ R)) и трябва да покажем дали тези твърдения подобни са или не.

Решение: Ще докажем това с помощта на таблица на истината, която е описана по следния начин:

П Q Р (P ⇒ Q) (Q ⇒ R) P ⇒ (Q ⇒ R) (P ⇒ Q) ⇒ R
Е Е Е T T T Е
Е Е T T T T T
Е T Е T Е T Е
Е T T T T T T
T Е Е Е T T T
T Е T Е T T T
T T Е T Е Е Е
T T T T T T T

В горната таблица на истината можем да видим, че таблицата на истината на P ⇒ (Q ⇒ R) и (P ⇒ Q) ⇒ R не са подобни. Следователно и двете ще генерират различни изходи или резултати.

Повече за импликацията

Още няколко примера за импликации са описани по-долу:

  • Ако е слънчево, тогава ще отида на училище.
  • Ако си намеря добра работа, тогава ще печеля пари.
  • Ако имам добри оценки, тогава родителите ми ще бъдат щастливи.

Във всички горни примери се объркваме, защото не знаем кога една импликация ще се счита за вярна и кога ще се счита за невярна. За да разрешим този проблем и да разберем понятието импликация, ще използваме хипотетичен пример. В този пример ще приемем, че Мари ще играе бадминтон с приятеля си Джак и неговият приятел Джак иска да мотивира Мари малко, така че той я примамва с изявление:

 'If you win then I will buy a ring for you'

Чрез това изявление Джак има предвид, че ако бракът спечели, тогава очевидно той ще си купи пръстен. Чрез това изявление Джак се ангажира само когато Мари спечели. Той не е извършил нищо в никакъв случай, когато Мери е на свобода. Така че в края на мача може да има само четири възможности, които са описани по следния начин:

  • Ожени се печели - купи си пръстен.
  • Женитбата печели - не купувайте пръстен.
  • Ожени се губи - купи пръстен.
  • Ожени се губи - не купувай пръстен.

Джак обаче не направи никакво изявление, свързано с правило (B). Той също така не спомена правила номер (C) и (D) в изявлението си, така че ако Marry загуби, тогава изцяло зависи от Джак дали ще й купи пръстен или не. Всъщност твърдения (A), (C) и (D) могат да се случат като резултат от изявлението, което Джак казва на Marry, но (B) няма да бъде резултатът. Ако се случи изход (B), само тогава Джак ще бъде хванат в лъжа. Във всички останали три случая, т.е. (A), (C) и (D), той ще е казал истината.

Сега ще използваме по-простото изявление, за да можем символично да дефинираме изявлението на Джак по следния начин:

 P: you win Q: I will buy a ring for you

В тази импликация използваме логическия символ ⇒, който може да се чете като „внушава“. Ще формираме изявлението Jack's Compound с помощта на поставяне на тази стрелка от P към Q по следния начин:

 P ⇒ Q: If you win, then I will buy a ring for you.

В заключение забелязахме, че импликацията ще бъде невярна само когато P е вярно и q е невярно. Според това твърдение Мари печели играта, но за съжаление Джак не купува пръстен. Във всички останали случаи/резултати твърдението ще бъде вярно. Съответно таблицата на истината за импликацията е описана, както следва:

П Q P ⇒ Q
T T T
T Е Е
Е T T
Е Е T

Списъкът със съответните логически уравнения за импликацията е описан, както следва:

 T → T = T T → F = F F → T = T F → F = T

Примери за импликация:

Има различни примери за последици и някои от тях са описани по-долу:

Пример 1: Да предположим, че има четири твърдения, P, Q, R и S където

П: Джак е на училище

Въпрос: Джак преподава

Р: Джак спи

П: Джак е болен

Сега ще опишем някои символични твърдения, които са включени в тези прости твърдения.

  1. P → R
  2. S → ~P
  3. ~Q → (S ∧ R)
  4. (P ∨ R) → ~Q
  5. (~R ∧ ~S) → (Q ∨ ~P)

Тук трябва да покажем представянето на интерпретацията на тези символични твърдения в думи.

Решение:

P → R Ако Джак е в училище, значи Джак преподава.
S → ~P Ако Джак е болен, значи не е на училище.
~Q → (S ∧ R) Ако Джак не преподава, значи е болен и спи.
(P ∨ R) → ~Q Ако Джак е на училище или спи, значи той не преподава.
(~R ∧ ~S) → (Q ∨ ~P) Ако Джак не спи и не е болен, значи преподава или не е на училище.

Пример 2: В този пример имаме импликация P → Q. Тук също имаме още три съставни твърдения, които са естествено свързани с тази импликация, която е контра положителна, обратна и обратна на импликацията. Връзката между всички тези четири твърдения е описана с помощта на таблица, която е описана по следния начин:

Внушение P → Q
Конверс Q → P
Обратно ~P → ~Q
Контрапозитивен ~Q → ~P

Сега ще разгледаме пример за импликация, който съдържа твърдението „Ако учиш добре, получаваш добри оценки“. Това твърдение е във формата P → Q, където

П: Учиш добре

Въпрос: получавате добри оценки

Сега ще използваме изразите P и Q и ще покажем четирите асоциирани израза така:

Извод: Ако учиш добре, получаваш добри оценки.

Обратно: Ако имаш добри оценки, учиш добре.

Обратно: Ако не учиш добре, не получаваш добри оценки.

Контрапозитивни: Ако не получаваш добри оценки, не учиш добре.

Истинните стойности на всички горепосочени асоциирани твърдения са описани с помощта на таблица на истината, която е описана по следния начин

П Q ~P ~Q P → Q Q → P ~P → ~Q ~Q → ~P
T T Е Е T T T T
T Е Е T Е T T Е
Е T T Е T Е Е T
Е Е T T T T T T

В горната таблица можем да видим, че импликацията (P → Q) и нейното противоположно (~Q → ~P) имат една и съща стойност в своите колони. Това означава, че и двете са еквивалентни. Така че можем да кажем, че:

 P → Q = ~Q → ~P

По подобен начин можем да видим, че обратното и обратното имат подобни стойности в своите колони. Но това няма да има никаква разлика, защото обратното е противоположното на обратното. По същия начин, първоначалното внушение може да се получи от контра-позитивното на контра-позитивното. (Това означава, че ако отхвърлим P и Q и след това сменим посоката на стрелката и след това отново ще повторим процеса, това означава да отхвърлим ~P и ~Q и отново сменим посоката на стрелката, в този случай ще получим обратно откъдето започнахме).