Претпоставимо да постоје две формуле, Кс и И. Ове формуле ће бити познате као еквиваленција ако је Кс ↔ И таутологија. Ако су две формуле Кс ↔ И таутологија, онда је можемо записати и као Кс ⇔ И, а ову релацију можемо читати као Кс је еквивалент И.
Напомена: Постоје неке тачке које треба да имамо на уму приликом линеарне еквиваленције формуле, а које су описане на следећи начин:
- ⇔ се користи само за означавање симбола, али није везивно.
- Истинитост Кс и И ће увек бити једнака ако је Кс ↔ И таутологија.
- Релација еквиваленције садржи два својства, то јест, симетричну и транзитивну.
Метод 1: Метод табеле истине:
У овој методи ћемо конструисати табеле истинитости било које формуле са два исказа, а затим проверити да ли су ови искази еквивалентни.
Пример 1: У овом примеру морамо доказати Кс ∨ И ⇔ ¬(¬Кс ∧ ¬И).
Решење: Табела истинитости за Кс ∨ И ⇔ ¬(¬Кс ∧ ¬И) је описана на следећи начин:
| Икс | И | Кс ∨ И | ¬Кс | ¬И | ¬Кс ∧ ¬И | ¬(¬Кс ∧ ¬И) | Кс ∨ И ⇔ ¬(¬Кс ∧ ¬И) |
|---|---|---|---|---|---|---|---|
| Т | Т | Т | Ф | Ф | Ф | Т | Т |
| Т | Ф | Т | Ф | Т | Ф | Т | Т |
| Ф | Т | Т | Т | Ф | Ф | Т | Т |
| Ф | Ф | Ф | Т | Т | Т | Ф | Т |
Као што видимо да је Кс ∨ И и ¬(¬Кс ∧ ¬И) таутологија. Отуда Кс ∨ И ⇔ ¬(¬Кс ∧ ¬И).
Пример 2: У овом примеру морамо доказати (Кс → И) ⇔ (¬Кс ∨ И).
Решење: Табела истинитости (Кс → И) ⇔ (¬Кс ∨ И) је описана на следећи начин:
| Икс | И | Кс → И | ¬Кс | ¬Кс ∨ И | (Кс → И) ⇔ (¬Кс ∨ И) |
|---|---|---|---|---|---|
| Т | Т | Т | Ф | Т | Т |
| Т | Ф | Ф | Ф | Ф | Т |
| Ф | Т | Т | Т | Т | Т |
| Ф | Ф | Т | Т | Т | Т |
Као што видимо да су Кс → И и (¬Кс ∨ И) таутологија. Отуда (Кс → И) ⇔ (¬Кс ∨ И)
Формула еквиваленције:
Постоје различити закони који се користе за доказивање формуле еквиваленције, која је описана на следећи начин:
Идемпотентни закон: Ако постоји једна формула исказа, она ће имати следећа својства:
X ∨ X ⇔ X X ∧ X ⇔ X
Асоцијативно право: Ако постоје три формуле исказа, онда ће имати следећа својства:
(X ∨ Y) ∨ Z ⇔ X ∨ (Y ∨ Z) (X ∧ Y) ∧ Z ⇔ X ∧ (Y ∧ Z)
Комутативно право: Ако постоје две формуле исказа, онда ће имати следећа својства:
X ∨ Y ⇔ Y ∨ X X ∧ Y ⇔ Y ∧ X
Дистрибутивни закон: Ако постоје три формуле исказа, онда ће имати следећа својства:
лист.сорт јава
X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) X ∧ (Y ∨ Z) ⇔ (X ∧ Y) ∨ (X ∧ Z)
Закон о идентитету: Ако постоји једна формула исказа, она ће имати следећа својства:
(a) (i) X ∨ F ⇔ X (ii) X ∨ T ⇔ T (b) (i) X ∧ T ⇔ X (ii) X ∧ F ⇔ F
Закон допуне: Ако постоји једна формула исказа, она ће имати следећа својства:
(a) (i) X ∨ ¬X ⇔ T (ii) X ∧ ¬X ⇔ F (b) (i) ¬(¬X) ⇔ X (ii) ¬T ⇔ F , ¬F ⇔ T
Закон о апсорпцији: Ако постоје две формуле исказа, онда ће имати следећа својства:
X ∨ (X ∧ Y) ⇔ X X ∧ (X ∨ Y) ⇔ X
Из Моргановог закона: Ако постоје две формуле исказа, онда ће имати следећа својства:
¬(X ∨ Y) ⇔ ¬X ∧ ¬Y ¬(X ∧ Y) ⇔ ¬X ∨ ¬Y
Метод 2: Процес замене
У овој методи, претпоставићемо формулу А : Кс → (И → З). Формула И → З може бити позната као део формуле. Ако овај део формуле, тј. И → З, заменимо помоћу формуле еквиваленције ¬И ∨ З у А, онда ћемо добити другу формулу, тј. Б : Кс → (¬И ∨ З). Лако је проверити да ли су дате формуле А и Б еквивалентне једна другој или не. Уз помоћ процеса замене, можемо добити Б од А.
Пример 1: У овом примеру морамо доказати да је {Кс → (И → З) ⇔ Кс → (¬И ∨ З)} ⇔ (Кс ∧ И) → З.
Решење: Овде ћемо узети леви бочни део и покушати да добијемо десни део.
X → (Y → Z) ⇔ X → (¬Y ∨ Z) [∵ Y → Z ⇔ ¬Y ∨ Z] ⇔ ¬X ∨ (¬Y ∨ Z) [∵ X → Y ⇔ ¬X ∨ Y]
Сада ћемо користити асоцијативни закон овако:
⇔ (¬X ∨ ¬Y) ∨ Z
Сада ћемо користити Де Морганов закон овако:
⇔ ¬(X ∧ Y) ∨ Z ⇔ (X ∧ Y) → Z [∵ X → Y ⇔ ¬X ∨ Y]
Отуда доказано
{X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z Пример 2: У овом примеру морамо доказати да је {(Кс → И) ∧ (З → И)} ⇔ (Кс ∨ З) → И.
Решење: Овде ћемо узети леви бочни део и покушати да добијемо десни део.
(X→ Y) ∧ (Z → Y) ⇔ (¬X ∨ Y) ∧ (¬Z ∨ Y) ⇔ (¬X ∧ ¬Z) ∨ Y ⇔ ¬(X ∨ Z) ∨ Y ⇔ X ∨ Z → Y
Отуда доказано
{(Кс → И) ∧ (З → И)} ⇔ (Кс ∨ З) → И
Пример 3: У овом примеру морамо доказати да је Кс → (И → Кс) ⇔ ¬Кс → (Кс → И).
Решење: Овде ћемо узети леви бочни део и покушати да добијемо десни бочни део.
X → (Y → X) ⇔ ¬X ∨ (Y → X) ⇔ ¬X ∨ (¬Y ∨ X) ⇔ (¬X ∨ X) ∨ ¬Y ⇔ T ∨ ¬Y ⇔ T and ¬X → (X → Y) ⇔ ¬(¬X) ∨ (X → Y) ⇔ X ∨ (¬X ∨ Y) ⇔ (X ∨ ¬X) ∨ Y ⇔ T ∨ Y ⇔ T
Отуда доказано
X → (Y → X) ⇔ ¬X → (X → Y)
Пример 4: У овом примеру морамо доказати да (¬Кс ∧ (¬И ∧ З)) ∨ (И ∧ З) ∨ (Кс ∧ З) ⇔ З.
Решење: Овде ћемо узети леви бочни део и покушати да добијемо десни део.
(¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z)
Сада ћемо користити асоцијативне и дистрибутивне законе овако:
⇔ ((¬X ∧ ¬Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Сада ћемо користити Де Морганов закон овако:
⇔ (¬(X ∨ Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Сада ћемо користити Дистрибутивни закон овако:
⇔ (¬(X ∨ Y) ∨ (X ∨ Y)) ∧ Z ⇔ T ∧ Z [∵ ¬X ∨ X ⇔ T ⇔ R
Отуда доказано
(¬P ∧ (¬Q ∧ R)) ∨ (Q ∧ R) ∨ (P ∧ R) ⇔ R
Пример 5: У овом примеру морамо показати да је ((Кс ∨И) ∧ ¬(¬Кс ∧ (¬И ∨ ¬З))) ∨ (¬Кс ∧ ¬И) ∨ (¬Кс ∧ ¬З) таутологија.
Решење: Овде ћемо узети мале делове и решити их.
Прво ћемо користити Де Морганов закон и добити следеће:
¬X ∧ ¬Y ⇔ ¬(X ∨ Y) ¬X ∨ ¬Z ⇔ ¬(X ∧ Z)
дакле,
(¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ ¬(X ∨ Y) ∨ ¬(X ∧ Z) ⇔ ¬((X ∨ Y) ∧ (X ∨ Z))
Такође
¬(¬X ∧ (¬Y ∨ ¬Z)) ⇔ ¬(¬X ∧ ¬(Y ∧ Z)) ⇔ X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Стога
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ⇔ (X ∨ Y) ∧ (X ∨ Y) ∧ (X ∨ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Тако
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ [(X ∨ Y) ∧ (X ∨ Z)] ∨ ¬[(X ∨ Y) ∧ (X ∨ Z)] [∵ ¬X ∨ X ⇔ T] ⇔ T
Отуда можемо рећи да је дата формула таутологија.
Пример 6: У овом примеру морамо показати да је (Кс ∧ И) → (Кс ∨ И) таутологија.
Решење: (Кс ∧ И) → (Кс ∨ И)
⇔ ¬(X ∧ Y) ∨ (X ∨ Y) [∵ X → Y ⇔ ¬X ∨ Y]
Сада ћемо користити Де Морганов закон овако:
⇔ (¬X ∨ ¬Y) ∨ (X ∨ Y)
Сада ћемо користити асоцијативни закон и комутативни закон овако:
⇔ (¬X ∨ X) ∨ (¬Y ∨ Y)
Сада ћемо користити закон негације овако:
⇔ (T ∨ T) ⇔ T
Отуда можемо рећи да је дата формула таутологија.
јавасцрипт принт
Пример 7: У овом примеру морамо написати негацију неких исказа, који су описани на следећи начин:
- Марри ће завршити своје образовање или прихватити писмо о придруживању компаније КСИЗ.
- Хари ће сутра отићи да се провоза или да трчи.
- Ако добијем добре оцене, мој рођак ће бити љубоморан.
Решење: Прво ћемо решити прву изјаву овако:
1. Претпоставимо да ће Кс: Марри завршити своје образовање.
И: Прихватите писмо о придруживању компаније КСИЗ.
Можемо користити следећи симболички облик да изразимо ову изјаву:
X ∨ Y
Негација Кс ∨ И је описана на следећи начин:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
У закључку, негација датог исказа ће бити:
¬X ∧ ¬Y: Marry will not complete her education, and she will not accept the joining letter of XYZ Company.
2. Претпоставимо Кс: Хари ће отићи да се провоза
И: Хари ће трчати сутра
Можемо користити следећи симболички облик да изразимо ову изјаву:
X ∨ Y
Негација Кс ∨ И је описана на следећи начин:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
У закључку, негација датог исказа ће бити:
¬X ∧ ¬Y: Harry will not go for a ride, and he will not run tomorrow
3. Претпоставимо Кс: Ако добијем добре оцене.
И: Мој рођак ће бити љубоморан.
Можемо користити следећи симболички облик да изразимо ову изјаву:
X → Y
Негација Кс → И је описана на следећи начин:
¬(X → Y) ¬(X → Y) ⇔ ¬(¬X ∨ Y) ⇔ X ∧ ¬Y.
У закључку, негација датог исказа ће бити:
X ∧ ¬Y: I get good marks, and my cousin will not be jealous.
Пример 8: У овом примеру морамо да запишемо негацију неких исказа уз помоћ Де Моргановог закона. Ове изјаве су описане на следећи начин:
- Треба ми дијамантски сет који вреди златни прстен.
- Добићете добар посао или нећете добити доброг партнера.
- Примам много посла и не могу да поднесем.
- Мој пас иде на пут или прави неред у кући.
Решење: Негирање свих исказа уз помоћ Де Моргановог закона описано је један по један овако:
- Не треба ми дијамантски сет или не вреди златни прстен.
- Не можете добити добар посао и добићете доброг партнера.
- Не радим пуно или могу то да поднесем.
- Мој пас не иде на пут и не прави неред у кући.
Пример 9: У овом примеру имамо неке исказе и морамо да напишемо негацију тих исказа. Изјаве су описане на следећи начин:
- Ако пада киша, онда се отказује план за одлазак на плажу.
- Ако вредно учим, добићу добре оцене на испиту.
- Ако одем на забаву до касно у ноћ, онда ћу добити казну од оца.
- Ако не желиш да разговараш са мном, онда мораш да блокираш мој број.
Решење: Негација свих изјава је описана један по један овако:
- Ако се план за одлазак на плажу откаже, онда пада киша.
- Ако добијем добре оцене на испиту, онда вредно учим.
- Ако ћу добити казну од оца, онда идем на забаву до касно у ноћ.
- Ако морате да блокирате мој број, онда не желите да разговарате са мном.
Пример 10: У овом примеру морамо да проверимо да ли су (Кс → И) → З и Кс → (И → З) логички еквивалентни или не. Наш одговор морамо да оправдамо уз помоћ табела истинитости и уз помоћ правила логике да поједноставимо оба израза.
Решење: Прво ћемо користити метод 1 да проверимо да ли су (Кс → И) → З и Кс → (И → З) логички еквивалентни, што је описано на следећи начин:
како искључити режим програмера за Андроид
Метод 1: Овде ћемо претпоставити следеће:
(X → Y) → Z ⇔ (¬X ∨ Y) → Z ⇔ ¬(¬X ∨ Y) ∨ Z ⇔ (X ∧ ¬Y) ∨ Z ⇔ (X ∧ Z) ∨ (¬Y ∧ Z)
И
X → (Y → Z) ⇔ X → (¬Y ∨ Z) ⇔ ¬X ∨ (¬Y ∨ Z) ⇔ ¬X ∨ ¬Y ∨ Z X → Y) → Z and X → (Y → Z)
2. метод: Сада ћемо користити други метод. У овој методи користићемо табелу истинитости.
| Икс | И | ВИТХ | Кс → И | (Кс → И) → З | И → З | Кс → (И → З) |
|---|---|---|---|---|---|---|
| Т | Т | Т | Т | Т | Т | Т |
| Т | Т | Ф | Т | Ф | Ф | Ф |
| Т | Ф | Т | Ф | Т | Т | Т |
| Т | Ф | Ф | Ф | Т | Т | Т |
| Ф | Т | Т | Т | Т | Т | Т |
| Ф | Т | Ф | Т | Ф | Ф | Т |
| Ф | Ф | Т | Т | Т | Т | Т |
| Ф | Ф | Ф | Т | Ф | Т | Т |
У овој табели истинитости можемо видети да колоне (Кс → И) → З и Кс → (И → З) не садрже идентичне вредности.