Двузначна логика



Дата20.07.2018
Размер186.4 Kb.
Двузначна логика

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


В наши дни може да се обобщи, че с логика означаваме общите закономерности на мисленето. Предмет на нашите занимания все пак не е логиката изобщо, а математическата логика - науката за правилните математически разсъждения и изводи.
Мнозина учени са дали своя принос за развитието на тази част от математиката, но сме длъжни да споменем ирландския математик Джордж Бул (1815 - 1864), който полага основите на математическата логика (неслучайно се среща и терминът Булева алгебра).

1. Съждение - изречение на естествен език, за което по безспорен начин може да се отговори дали е вярно или не.



Следователно следните изречения :

Това е черна котка.


Днес е слънчево.
Десет се дели на две. са съждения, докато изложените по-долу:

Бягай !
Добре ли си ?


Не съществуват извънземни. не са.

Особено показателен е случаят с последното изречение - тъй като няма безспорен отговор на въпроса има или няма извънземни, изречението не може да бъде разглеждано като съждение.

Ако едно съждение е вярно, казваме че то има верностна стойност истина, а ако не е вярно, казваме че верностната му стойност е неистина (лъжа).

За означаване на стойността истина се използва Т (true - истина(англ.)) или 1, а за означаване на стойността неистина се използва F (false - лъжа(англ.)) или 0.

Тъй като всяко съждение може да има верностна стойност истина или неистина (1 или 0), то наричаме логиката двузначна или още двоична.

Пример: Съждението ,,12 се дели на 5" има верностна стойност 0, докато съждението ,,Слънцето изгрява от изток" - 1 .

Стойностите 1(Т) и 0(F) се наричат съждителни константи, а променливите, които приемат само такива стойности,се наричат съждителни променливи.

2. Прости и сложни (съставни) съждения


Лесно може да се забележи, че съжденията се различават доста едно от друго.
Например ,,Иван е чернокос" и ,,Тони също е чернокос, но сега се е изрусил"
Първото е пределно кратко и не съдържа в себе си друго съждение, докато второто сякаш е съставено от две - ,,Тони е чернокос" и ,,Тони се е изрусил" .

Съждения, които не съдържат в себе си други съждения, се наричат прости.



Сложни или съставни се наричат такива съждения, които се състоят от поне две прости съждения.
Следователно ,,Навън вали" е просто съждение, докато ,,Навън вали и аз имам чадър" е съставно съждение.

3. Логически операции (функции)


Начините по които човек може да свързва простите съждения в сложни, както и необходимостта от това да знае как да определи верностната стойност на едно сложно съждение, ако знае стойностите на съставящите го прости, водят до изучаване и класифициране на логическите функции.

 

4. Запознаване с някои от основните логически функции на две променливи


а) логическо отрицание - има един аргумент и променя стойността му от 1 в 0 или обратно от 0 в 1. Срещат се различни варианти на означаване - !,NOT,¬ и др. Например ако а е съждителна променлива, то отицанието на а можем да запишем по следните начини: !а, NOTa,¬а и др.. По-нататък е използвано означението !, тъй като в езика за програмиране С, който ще бъде предмет на изучаване, е използвано точно това означение за логическото отрицание.

Правилата, по които действа всяка функция най-лесно се описват с т.нар. таблица на истинност, в която се изреждат всички възможни комбинации от стойности на променливите и срещу всяка се показва стойността на функцията.



Таблица за истинност


a

!a

0

1

1

0

Пример: а=,,Днес е топло" !а=,,Днес не е топло"
а=,,Не обичам сладолед" !а=,,Обичам сладолед"

Особен интересно е да се образуват отрицания на изрази в които участват термини като: всеки, никой, някой, съществува, винаги, никога и т.н.

Пример: а=,,Всички момчета харесват футбола"
            !а=,,Някои момчета не харесват футбола"

а=,,Никога не вали в Сахара"


!а=,, Понякога вали в Сахара"

б) логическо ,,или" - дизюнкция - има два аргумента и има стойност 1, когато поне един от аргументите й има стойност 1, и 0, когато и двата аргумента са равни на 0.


Означава се с Ú или с OR, например aORb или aÚb.

Таблица за истинност

a

b

aÚb

0

0

0

0

1

1

1

0

1

1

1

1

Пример: с=,,Тони е на плаж или е някъде с приятели"


Ако а=,,Тони е на плаж" , а b=,,Тони е някъде с приятели" , то с= аÚb. Наистина съждението с ще има стойност 0 само ако Тони не е на плаж, нито е с приятели, т.е. само когато и двете съставящи го съждения имат стойност 0.

в) логическо ,,и" - конюнкция - има два аргумента и има стойност 0, когато поне един от аргументите й има стойност 0, и 1, когато и двата аргумента са равни на 1.


Означава се с Ù или с AND, например aANDb или aÙb.

Таблица за истинност

a

b

aÙb

0

0

0

0

1

0

1

0

0

1

1

1

Пример: с=,,Момчил е рус и синеок"


Ако а=,,Момчил е рус" , а b=,,Момчил е синеок" , то с= аÙb. Наистина съждението с ще има стойност 1, само ако Момчил е едновременно рус и синеок, т.е. само когато и двете съставящи го съждения имат стойност 1.

г) равнозначност - има два аргумента и има стойност 0, когато аргументите й имат различни стойности, и 1, когато аргументите й са равни.


Означава се с «.

Таблица за истинност

a

b

a«b

0

0

1

0

1

0

1

0

0

1

1

1

Пример: Съждението с=,,Един четириъгълник е успоредник тогава и само тогава, когато диагоналите му се разполовяват взаимно" може да се разглежда като а«b, където а=,,Един четъриъгълник е успоредник" и b=,,Диагоналите на един четириъгълник се разполовяват взаимно". Очевидно, ако е вярно само а, или само b, то резултатното с ще има стойност 0, докато ако а и b имат равни стойности, то с е 1.

д) изключващо ,,или"( изкл. дизюнкция, неравнозначност, събиране по модул 2) - има два аргумента и има стойност 0, когато аргументите й имат равни стойности, и 1, когато аргументите й са различни.


Означава се с Å или с XOR.

Таблица за истинност

a

b

aÅb

0

0

0

0

1

1

1

0

1

1

1

0

Пример: Ако а=,,Сега Петър е във Варна" и b=,,Сега Петър е в София" , то съждението с=,,Сега Петър е във Варна или в София" може да се разглежда като с=аÅb. Ако е вярно само а, или само b, то с е вярно, но ако и двете (а и b) са неверни, или пък и двете са верни, то с е 0 ( Петър не може да бъде едновременно и на двете места).

е) импликация ( следва, ако … , то …) - има два аргумента, катопървият се нарича предпоставка, а вторият - следствие. Резултатът от имплимацията е 0, само когато предпоставката е вярна (1), а следствието е грешно (0). В останалите случаи импликацията има стойност 1.


Означава се с ®.

Таблица за истинност

a

b

a®b

0

0

1

0

1

1

1

0

0

1

1

1

Пример: Ако а=,,Имаш двойка за годината" и b=,,Ще се явяваш на поправка" , то съждението с=,,Ако имаш двойка за годината, то ще се явяваш на поправка" може да се разглежда като с=а®b. Ако е вярно само а, то с е невярно, докато в останалите случаи с е вярно.


Наистина, ако някой има 2 за годината, то единствената възможност е да се яви на поправка, докато ако няма двойка,може да не се явява, но може и да се явява (ако е направил твърде много отсъствия например).

5. Задачи за упражнение

а) Открийте кои операции са използвани за образуване на всяко от сложните съждения:
· ,,Вазов е поет или писател"
· ,,Обичам да карам кола, но нямам своя собствена"
· ,,Ако закупите стока за повече от 50 лв, ще получите подарък"
· ,,Това е заек или котка"
· ,,Един равнобедрен триъгълник е равностранен тогава и само тогава, когато един от ъглите му е равен на 60° "

б) Ако са дадени съжденията а=,,Ще си науча по химия" и b=,,Ще отида на кино" , запишете как ще изглеждат сложните съждения, съставени по моделите:
· aÚb
· aÙb
· !aÙb
· aÅb
· a®b

Логически (съждителни) изрази
Основни свойства на логическите функции

Да се пресметне стойността на един съждителен израз означава да се замести всяка съждителна променлива с дадената и стойност и да се извършат означените операции.

Пример:
1.Да се пресметнат стойностите на изразите при така определените x и y:

(x Ú y) Ù (x Ú (!x Ù ( y®x))) = ? x=1; y=0

(x Ú y) Ù (x Ú (!x Ù ( y®x))) = (1 Ú 0) Ù (1 Ú (!1 Ù (0®1))) = 1 Ù (1 Ú (0 Ù 1)) =1 Ù (1Ú0)=

   =1 Ù 1 = 1

((x«y)Å(xÚ!y) Ù ((!xÚ!y) Ù !(xÅy))=? x=0; y=1

((x«y)Å(xÚ!y) Ù ((!xÚ!y) Ù !(xÅy))= ((0«1)Å(0Ú!1) Ù ((!0Ú!1) Ù !(0Å1))=

= (0 Å 0) Ù ( 1 Ù !1)=0 Ù (1 Ù 0) = 0 Ù 0 = 0

2.Да се пресметнат всички възможни стойности на израза pÚ(q ®r)


Най-удобно е решението на тази задача да се разположи в таблица,като в първите и колони разполагаме стойностите на участващите в израза съждителни променливи. Тъй като всяка съждителна променлива може да приема само 2 различни стойности, броят на редовете на таблицата може да бъде изчислен с помощта на израза 2n , където n е броят на променливите. С други думи, за израз, съдържащ 2 променливи е нужна таблица с 4 реда, ако променливите са 3, редовете на таблицата стават вече 8 и т.н.
Обикновено стойностите на израза се разполагат в последната колона.

p

q

r

q®r

pÚ(q®r)

0

0

0

1

1

0

0

1

1

1

0

1

0

0

0

0

1

1

1

1

1

0

0

1

1

1

0

1

1

1

1

1

0

0

1

1

1

1

1

1

Два съждителни израза са еквивалентни, ако получават еднакви стойности при всички възможни комбинации от стойности на участващите в тях променливи.

Ще разгледаме някои важни свойства на част от изучените логически функции, за да можем да пресмятаме по-лесно и сигурно сложни логически изрази, както и да решаваме други логически задачи .

1. Основни свойства


  1. 1)      xÚy=yÚx xÙy=yÙx

  2. 2)      xÙ0=0 xÚ0=x

  3. 3)      xÙ1=x xÚ1=1

  4. 4)      xÙ!x=0 xÚ!x=1

  5. 5)      !(!x)=x

  6. 6)      xÙx=x xÙx=x

  7. 7)      (xÙy)Ùz=xÙ(yÙz)=(xÙz)Ùy=xÙyÙz

  8.       (xÚy)Úz=xÚ(yÚz)=(xÚz)Úy=xÚyÚz

  9. 8)      xÙ(yÚz)=(xÙy)Ú(xÙz) xÚ(yÙz)=(xÚy)Ù(xÚz)

Доказателството се свежда до това да покажем, че във всяко едно равенство изразите, заемащи двете му страни, са еквивалентни. Най-лесно и прегледно това доказателство става, като записването се оформи в таблица, наречена верностна таблица. В първите колони изброяваме всички възможни комбинации от стойности на участващите променливи (както описахме по-горе, комбинациите са 2n), а в следващите попълваме стойностите на съответния израз. Тогава два израза ще са равни, ако колоните с техните стойности съвпадат изцяло.

Пример: Доказателства за св-ва 1)



x

y

xÚy

yÚx

xÙy

yÙx

0

0

0

0

0

0

0

1

1

1

0

0

1

0

1

1

0

0

1

1

1

1

1

1

От попълнената таблица ясно се вижда, че xÚy=yÚx и xÙy=yÙx.

По подобен начин се доказват и всички други свойства, като задължително е да се внимава да бъдат изредени всички възможни стойности на променливите. Опитайте сами!



За да проверите все пак!

След като вече имаме доказани група свойства, доказването на равенства между логически изрази може да се извършва по два начина - чрез преобразуване на единия или и двата израза с помощта на свойствата или чрез попълване на таблици с всички възможни стойности за двата израза.

Пример:
Да се докаже, че x Ú (x Ù y) = x .
Ще решим задачата и по двата описани по-горе начина.
I вариант - преобразувание
x Ú ( x Ù y ) = ( x Ù 1 ) Ú ( x Ù y ) = x Ù ( 1 Ú y ) = x Ù 1 = x
Най-напред прилагаме св-во 3) и представяме x като x Ù 1. После прилагаме св-во 8) в обратна посока ( изнасяме пред скобите x Ù) , след това заменяме 1 Ú y с 1 (според св-во 3) ) и пак по св. 3 получаваме от x Ù 1 само х.

II вариант - таблица



x

y

x Ù y

x Ú (x Ù y)

0

0

0

0

0

1

0

0

1

0

0

1

1

1

1

1

Явно стойностите в първата и последната колони съвпадат, следователно доказано е равенството x Ú ( x Ù y ) = x .

Закони на де Морган

Август де Морган (1806 - 1871) е английски математик, работил в областта на символичните изчисления в логиката. Неговото име носят два важни закона, даващи връзка между логическото отрицание, логическото ,,и" и логическото ,,или".

1.   ! ( x Ù y ) = !x Ú !y

2.   ! ( x Ú y ) = !x Ù !y

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



x

y

x Ù y

!(xÙy)

x Ú y

!(xÚy)

!x

!y

!x Ú !y

!x Ù !y

0

0

0

1

0

1

1

1

1

1

0

1

0

1

1

0

1

0

1

0

1

0

0

1

1

0

0

1

1

0

1

1

1

0

1

0

0

0

0

0

Примери за приложение на законите на де Морган

1. Да се докаже равенството



(xÙy) Ú !(xÚ!y) = y

(xÙy) Ú !(xÚ!y) = (xÙy) Ú (!x Ù !(!y)) = (xÙy) Ú (!xÙy) = (xÚ!x) Ù y = 1Ùy = y



2. Aко са дадени съжденията а=,,Х е по-голямо от 2" и b=,,Х е по-малко от 4" да се представи чрез а и b съждението А=,,Х принадлежи на интервала (2;4)", както и неговото отрицание.
Тъй като едно число принадлежи на интервала (2;4) само когато е едновременно по-голямо от 2 и по-малко от 4, то за да бъде изпълнено А, трябва да бъдат изпълнени и а и b. Тогава А=а Ùb.
За изразяването на !А има два пътя.
I вариант !А=!(а Ùb)=!a Ú !b
II вариант !А=,,Х не принадлежи на интервала (2;4)" Това е изпълнено, когато съответната стойност е или по-малка или равна на 2 или е по-голяма или равна на 4 т.е. изпълнени са или !а или !b. Тогава е ясно, че !А=!a Ú !b.

3. Дадено е съждението А=,,Мирослав е българин от Своге" . Представете А чрез две прости съждения и запишете как изглежда !А.
Ако а= ,,Мирослав е българин" , а b= ,,Мирослав е от Своге" , то А=а Ùb .

Тогава !А = !(а Ùb) = !a Ù !b и като текст !А би изглеждало така: ,, Мирослав не е българин или не е от Своге"



4. Съставете отрицанията на съжденията:
а) А=,,Ангел слуша техно или рап"
б) А=,,Иван е взел книжка и си е купил кола"

а) Можем да представим съждението така А=,,Ангел слуша техно" Ú ,,Ангел слуша рап". Следователно по законите на де Морган !А= !,,Ангел слуша техно" Ù !,,Ангел слуша рап" , тоест !А=,,Ангел не слуша техно" Ù ,,Ангел не слуша рап" . На нормален говорим език !А бихме изказали така: ,,Ангел не слуша нито техно, нито рап".
б) Аналогично на горните разсъждения можем да представим А във вида А=аÙс, където а=,,Иван е взел книжка" и с=,,Иван си е купил кола". Съвсем лесно се намира , че !А=!(а Ùс)= !а Ú !с. Ако се опитаме да изкажем !А с думи, то би трабвало да изглежда така: ,,Иван не е взел книжка или не си е купил кола" . Струва си да се отбележи, че доста хора биха допуснали грешка и биха съставили !А като ,,Иван не е взел книжка, нито си е купил кола" , което вече би било твърде пресилено (особено спрямо незнайния Иван!) .

Ако ви е интересно можете да разгледате какво контролно са правили ученици в МГ (тук)
Проверете какви задачи от логика има в примерната матура по информатика (тук)


База данных защищена авторским правом ©obuch.info 2016
отнасят до администрацията

    Начална страница