Еквивалентни, TI и TL формули на алгебрата на логиката. Основни еквивалентности. (Закони на логическите операции). Законът за дуалността. Булева алгебра Закон за единичните елементи

Логики- наука, която изучава законите и формите на мисленето; учението за методите на разсъждението и доказателствата.

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

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

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

По обем се разграничават следните отношения на понятия:

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

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

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

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

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

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

Всяко предложение е или вярно, или невярно; не може и двете едновременно.

В естествения език изказванията се изразяват в декларативни изречения. Възклицателните и въпросителните изречения не са твърдения.

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

Изявлението се нарича просто(елементарно), ако никоя част от него сама по себе си не е твърдение.

Твърдение, съставено от прости твърдения, се нарича композитен(труден).

Простите твърдения в алгебрата на логиката се означават с главни латински букви:
НО= (Аристотел е основателят на логиката),
AT= (Бананите растат на ябълкови дървета).

Обосноваването на истинността или неистинността на прости твърдения се решава извън алгебрата на логиката. Например истинността или неистинността на твърдението: „Сборът от ъглите на триъгълника е 180 градуса“ се установява от геометрията и – в геометрията на Евклид това твърдение е вярно, а в геометрията на Лобачевски е невярно.

На вярно твърдение се присвоява 1, на грешно - 0. По този начин, НО = 1, AT = 0.

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

Основни операции на пропозиционалната алгебра.

Логическа операция КОНЮНКЦИЯ(лат. conjunctio - обвързвам):

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

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

Таблица на истинността на връзката:

НО	AT	НО&AT
0	0	0
0	1	0
1	0	0
1	1	1

Логическа операция ДИЗЮНКЦИЯ(лат. disjunctio - различавам):

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

Таблица на истината на дизюнкция:

НО	AT	НОAT
0	0	0
0	1	1
1	0	1
1	1	1

Логическа операция INVERSE(лат. inversio - обръщам):

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

Таблица на отрицателната истина:

НО	не А
0	1
1	0

Функцията за логическо събиране OR (LogValue1;LogValue2;…) дава резултат TRUE (True) само когато поне един булев аргумент е TRUE (1).

Функцията за логическо отрицание NOT(LogValue) се оценява на TRUE (True), когато логическият аргумент е FALSE (0) и, обратно, стойността FALSE (False), когато логическият аргумент е TRUE (1).

Логическа операция ПОСЛЕДСТВИЕ(лат. implicatio - тясно свързвам):

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

Импликационна таблица на истината:

НО	AT	НОAT
0	0	1
0	1	1
1	0	0
1	1	1

Логическа операция ЕКВИВАЛЕНТНОСТ(лат. aequivalens - еквивалент):

в естествения език съответства на обрати на речта тогава и само тогаваи ако и само ако;
обозначаване: ~ ;
друго име: еквивалентност.

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

Таблица на истината за еквивалентност:

НО	AT	НО~AT
0	0	1
0	1	0
1	0	0
1	1	1

Логическите операции имат следния приоритет: действия в скоби, инверсия, &, , ~.

Таблица, показваща какви стойности приема съставен израз за всички комбинации (набори) от стойности на неговите прости изрази, се нарича таблица на истинатасъставно сказуемо.

Съставните твърдения в алгебрата на логиката се записват с помощта на логически изрази. За всеки логически израз е достатъчно просто да се изгради таблица на истината.

Алгоритъмът за изграждане на таблица на истината:

пребройте броя на променливите нв логически израз;
определя броя на редовете в таблицата м = 2 н ;
пребройте броя на логическите операции във формулата;
установете последователността на изпълнение на логическите операции, като вземете предвид скоби и приоритети;
определете броя на колоните в таблицата: броя на променливите плюс броя на операциите;
изпишете набори от входни променливи, като вземете предвид факта, че те са естествена серия от n-битови двоични числа от 0 до 2 н -1;
попълнете таблицата на истината по колони, като извършвате логически операции в съответствие с последователността, установена в точка 4.

Наборите от входни променливи, за да се избегнат грешки, се препоръчва да бъдат изброени, както следва:
а) определя броя на наборите от входни променливи;
б) разделете колоната със стойности на първата променлива наполовина и попълнете горната част на колоната с 0, а долната част -1;
в) разделете колоната със стойности на втората променлива на четири части и попълнете всяка четвърт с редуващи се групи от 0 или 1, като започнете с група 0;
г) продължете да разделяте колоните със стойности на следващите променливи с 8, 16 и т.н. части и попълването им с групи 0 или 1, докато групите 0 и 1 не се състоят от един знак.

Пример.За формулата A&(B C) изградете таблица на истината алгебрично и с помощта на електронни таблици.

Броят на булевите променливи е 3, следователно броят на редовете в таблицата на истината трябва да бъде 2 3 = 8.

Броят на логическите операции във формулата е 5, следователно броят на колоните в таблицата на истината трябва да бъде 3 + 5 = 8.

НО	AT	° С	AT° С	НО & (AT° С)
0	0	0	1	0
0	0	1	0	0
0	1	0	1	0
0	1	1	1	0
1	0	0	1	1
1	0	1	0	0
1	1	0	1	1
1	1	1	1	1

Булева функцияизвикайте функцията F(X 1, X 2, ..., X n), чиито аргументи X 1, X 2, ..., X n(независими променливи) и самата функция (зависима променлива) приемат стойности 0 или 1.

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

Логическите функции могат да бъдат зададени таблично или аналитично - под формата на подходящи формули.

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

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

Булеви изразиНаречен еквивалентен, ако техните стойности на истината съвпадат за всякакви стойности на логическите променливи, включени в тях.

В алгебрата на логиката има редица закони, които позволяват еквивалентни трансформации на логически изрази. Нека представим отношенията, отразяващи тези закони.

Законът за двойното отрицание:
не (не А) = А.
Двойното отрицание изключва отрицанието.
Комутативен (комутативен) закон:
- за логическо добавяне:
A B = B A;

A&B=B&A.
Резултатът от операцията върху изрази не зависи от реда, в който са взети тези изрази.
Асоциативен (асоциативен) закон:
- за логическо добавяне:
(A B) C = A (B C);
За логическо умножение:
(A & B) & C = A & (B & C).
При едни и същи знаци скобите могат да се поставят произволно или дори да се пропуснат.
Разпределителен (разпределителен) закон:
- за логическо добавяне:
(A B) & C = (A & C) (B & C);
За логическо умножение:
(A & B) C = (A C) & (B C).
Дефинира правилото за поставяне в скоби на общо твърдение.
Закон за общата инверсия (закони на де Морган):
- за логическо добавяне:
;
За логическо умножение:
.
Законът за идемпотентността (от латинските думи idem - същият и potens - силен; буквално - еквивалентен):
- за логическо добавяне:
A A = A;
За логическо умножение:
A&A=A.
Законът означава липса на показатели.
Закони за постоянно изключване:
- за логическо добавяне:
A 1 = 1, A 0 = A;
За логическо умножение:
A&1 = A, A&0 = 0.
Законът на противоречието:
A & (не A) = 0.
Невъзможно е противоречиви твърдения да бъдат верни едновременно.
Закон за изключване на третото:
А (не А) = 1.
От двете противоречиви твърдения за една и съща тема едното винаги е вярно, а второто е невярно, третото не е дадено.
Закон за абсорбция:
- за логическо добавяне:
A(A&B)=A;
За логическо умножение:
A & (A B) = A.
Законът за изключване (залепване):
- за логическо добавяне:
(A & B) (& B) = B;
За логическо умножение:
(A B) & (B) = B.
Закон за противопоставяне (правило за обръщане):
(AB) = (BA).
Валидността на горните закони може да се докаже в табличен вид: напишете всички набори от стойности A и B, изчислете стойностите на лявата и дясната част на доказвания израз върху тях и се уверете, че получените колони съвпадат.

Пример.Опростете булевия израз:

Ефимова О., Морозов В., Угринович Н. Курс по компютърни технологии с основите на информатиката. Учебник за старши класове. - M .: LLC "Издателска къща AST"; ABF, 2000 г
Задачна тетрадка-ателие по информатика. В 2 тома / Ред. И.Семакина, Е.Кенър. - М .: Лаборатория за основни знания, 2001
Угринович Н. Информатика и информационни технологии. 10-11 клас - М .: Лаборатория за основни знания, АО "Московски учебници", 2001 г.

Задачи и тестове по темата "Основи на формалната логика"

Access DBMS Logic - Логико-математически модели 10 клас
Уроци: 5 Задачи: 9 Теста: 1
Решаване на логически задачи със средствата на математическата логика
Уроци: 4 Задачи: 6 Тестове: 1

Уважаеми студент!

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

Темата "Компютърни комуникации. Интернет" е от голям интерес напоследък, много млади хора прекарват почти цялото си свободно време в глобалната мрежа. Бих искал да ви напомня, че владеенето на интернет предполага не само способността да „сърфирате“ в мрежата и да посещавате интересни „чатове“ от време на време, но и да разберете принципите на организиране на информация в глобалната мрежа, да разберете нейната структура, протоколи, да може да конфигурира браузъра и програмите за електронна поща, да познава и спазва етиката на работа в Интернет и разбира се да използва мрежата за нейното най-важно предназначение – да разширява кръгозора си.

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

Темата "Логика" обикновено предизвиква известно объркване сред учениците, не всеки разбира важността на изучаването на тази тема. Бих искал да отбележа, че познаването на логиката е важно не само като основа за по-нататъшно изучаване на езиците за програмиране и принципите на работа с бази данни, но и като "симулатор" за развитието на специален тип мислене. Човек, който е отличен в изучаването на логиката, има огромни предимства в комуникацията. Много е ласкателно да чуете по свой адрес: „Логично е“, „има логика в разсъжденията ви“.

Урокът по информатика е предназначен за ученици от 10 клас на общообразователно училище, чиято учебна програма включва раздела "Алгебра на логиката". Тази тема е много трудна за учениците, така че аз като учител исках да ги заинтересувам да изучават законите на логиката, да опростяват логически изрази и да подхождат с интерес към решаването на логически проблеми. В обичайната форма даването на уроци по тази тема е досадно и обезпокоително, а някои определения не винаги са ясни на децата. Във връзка с предоставянето на информационно пространство, имах възможността да публикувам уроците си в обвивката „учене“. Студентите, които се регистрират в него, могат да посещават този курс в свободното си време и да препрочитат това, което не е ясно в урока. Някои ученици, пропуснали уроци поради болест, компенсират пропуснатата тема у дома или в училище и винаги са готови за следващия урок. Тази форма на обучение много подхождаше на много деца и тези закони, които бяха неразбираеми за тях, сега се научават в компютърна форма много по-лесно и по-бързо. Предлагам един от тези уроци по информатика, който се провежда интегрирано с ИКТ.

План на урока

Обяснение на нов материал, с участието на компютър - 25 минути.
Основни понятия и дефиниции, заложени в „обучение” – 10 минути.
Материал за любопитните - 5 минути.
Домашна работа – 5 минути.

1. Обяснение на нов материал

Закони на формалната логика

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

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

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

Законът за непротиворечивостта: невъзможно е едно и също око едновременно да бъде и да не е присъщо на едно и също нещо в едно и също отношение. Тоест, невъзможно е едновременно да се твърди и отрича нещо.

Закон за изключената среда: от две противоречиви твърдения едното е вярно, другото е невярно, а третото не е дадено.

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

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

Закони на пропозиционалната алгебра

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

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

Законите на алгебрата на твърденията (алгебрата на логиката) са тавтологии.

Понякога тези закони се наричат теореми.

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

Първите четири от следните закони са основните закони на пропозиционалната алгебра.

Закон за идентичността:

Всяка концепция и преценка са идентични на себе си.

Законът за тъждеството означава, че в процеса на разсъждение човек не може да замени една мисъл с друга, едно понятие с друго. Ако този закон е нарушен, са възможни логически грешки.

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

В дискусия: Движението е вечно. Ходенето на училище е движение. Следователно ходенето на училище е завинагидумата "движение" се използва в два различни смисъла (първият - във философския смисъл - като атрибут на материята, вторият - в обикновен смисъл - като действие за движение в пространството), което води до погрешно заключение.

Закон за непротиворечие:

Едно твърдение и неговото отрицание не могат да бъдат истинни едновременно. Тоест, ако твърдението НОе вярно, тогава неговото отрицание не Атрябва да е невярно (и обратното). Тогава техният продукт винаги ще бъде фалшив.

Именно това равенство често се използва при опростяване на сложни логически изрази.

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

1. Има живот на Марс и няма живот на Марс.

2. Оля е завършила гимназия и е в 10 клас.

Законът на изключената среда:

В един и същи момент твърдението може да бъде вярно или невярно, няма трето. Вярно също НО,или не А.Примери за прилагане на закона за изключената среда:

1. Числото 12345 е четно или нечетно, трето няма.

2. Компанията работи на загуба или на рентабилност.

3. Тази течност може или не може да бъде киселина.

Законът за изключената среда не е закон, признат от всички логици като универсален закон на логиката. Този закон се прилага, когато знанието се занимава с твърда ситуация: "или - или", "вярно-невярно". Когато има несигурност (например при разсъждения за бъдещето), законът на изключената среда често не може да бъде приложен.

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

Парадокс(Гръцки paradoxos - неочакван, странен) в този пример възниква от факта, че изречението се отнася за себе си. Друг известен парадокс е проблемът с фризьора: В един град фризьор подстригва всички жители, с изключение на тези, които се подстригват сами. Кой подстригва бръснаря?В логиката, поради своята формалност, не е възможно да се получи формата на такова самореферентно твърдение. Това още веднъж потвърждава идеята, че с помощта на алгебрата на логиката е невъзможно да се изразят всички възможни мисли и аргументи. Нека покажем как въз основа на дефиницията на пропозиционалната еквивалентност могат да бъдат получени останалите закони на пропозиционалната алгебра.

Например, нека дефинираме какво е еквивалентно на (еквивалентно на) НО(два пъти не НО,т.е. отрицание на отрицанието НО).За да направим това, ще изградим таблица на истината:

По дефиницията на еквивалентността трябва да намерим колоната, чиито стойности съвпадат със стойностите на колоната НО.Това ще бъде колоната НО.

Така можем да формулираме двойно правоотрицания:

Ако отхвърлим дадено твърдение два пъти, тогава резултатът е оригиналното твърдение. Например изявлението НО= Матроскин- коткае еквивалентно на казване A = Не е вярно, че Матроскин не е котка.

По подобен начин могат да бъдат извлечени и проверени следните закони:

Постоянни свойства:

Закони на идемпотентността:

Колкото и пъти да повтаряме: Включен телевизор или включен телевизор или включен телевизор...смисълът на изречението няма да се промени. Също и от повторение Навън е топло, навън е топло...нито един градус по-топло.

Законите на комутативността:

A v B = B v A

A & B = B & A

операнди НОи ATв операциите на дизюнкция и конюнкция могат да бъдат разменени.

Закони за асоциативност:

A v(B v C) = (A v B) v C;

A & (B & C) = (A & B) & C.

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

Закони за разпределение:

A v (B & C) = (A v B) & (A v C)

(разпределителна дизюнкция
относно връзката)

A & (B v C) = (A & B) v (A & C)

(дистрибутивност на връзката
относно дизюнкция)

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

Закони за абсорбция:

A v (A & B) = A

A & (A v B) = A

Извършете доказателството на законите за поглъщане сами.

Законите на Де Морган:

Словесни формулировки на законите на де Морган:

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

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

1) Изявление Не е вярно, че знам арабски или китайские идентичен с твърдението Не знам арабски и не знам китайски.

2) Изявление Не е вярно, че съм си научил урока и съм получил 5е идентичен с твърдението Или не съм си научил урока, или не съм получил пет.

Замяна на импликация и операции за еквивалентност

Операциите на импликация и еквивалентност понякога не са сред логическите операции на конкретен компютър или компилатор от език за програмиране. Тези операции обаче са необходими за решаване на много проблеми. Има правила за замяна на тези операции с последователности от операции на отрицание, дизюнкция и конюнкция.

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

За да замените операцията еквивалентностима две правила:

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

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

Помислете за следния пример.

Нека бъде дадено изявлението:

E = Не е вярно, че ако спечеля състезанието, ще получа награда.

Позволявам НО= Ще спечеля състезанието

B = Ще получа награда.

Следователно E = ще спечеля състезанието, но няма да получа награда.

Следните правила също представляват интерес:

Можете също да докажете тяхната валидност с помощта на таблици на истината.

Изразът им на естествен език е интересен.

Например фразата

Ако Мечо Пух е ял мед, значи е пълен

е идентичен с фразата

Ако Мечо Пух не е пълен, значи не е ял мед.

Упражнение:помислете за фрази-примери за тези правила.

2. Основни понятия и определенияв Приложение 1

3. Материал за любопитнитев Приложение 2

4. Домашна работа

1) Научете законите на логиката, като използвате курса по алгебра на логиката, намиращ се в информационното пространство (www.learning.9151394.ru).

2) Проверете доказателството на законите на Де Морган на компютър, като съставите таблица на истината.

Приложения

Основни понятия и определения (

§ четири. Еквивалентни, TI и TL формули на алгебрата на логиката. Основни еквивалентности. (Закони на логическите операции). Законът за дуалността.

Определение.

Две формули от алгебрата на логиката A и B се наричат ЕКВИВАЛЕНТНИ, ако приемат едни и същи логически стойности за всеки набор от елементарни предложения, включени във формулите. Еквивалентността на формулите ще бъде отбелязана със знака º, а обозначението A ºB означава, че формулите A и B са еквивалентни.

Формула А се нарича ИДЕНТИЧНО ИСТИННА (или ТАВТОЛОГИЯ), ако приема стойност 1 за всички стойности на променливите, включени в нея.

Една формула се нарича ИДЕНТИЧНО НЕВЯРНА (или ПРОТИВОРЕЧИЕ), ако приема стойност 0 за всички стойности на променливите, включени в нея.

Между понятията еквивалентност и еквивалентност има следната връзка: ако формулите A и B са еквивалентни, то формулата A"B е тавтология и обратно, ако формулата A"B е тавтология, то формулите A и B са еквивалентни.

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

1. Основни еквивалентности.

Закони на идемпотентността.

Закон на противоречието

Закон за изключената среда

двоен отрицателен закон

закони за усвояване

2. Еквивалентности, изразяващи някои логически операции по отношение на други.

Тук 3, 4, 5, 6 са законите на Морган.

Ясно е, че еквивалентности 5 и 6 се получават съответно от еквивалентности 3 и 4, ако вземем отрицания от двете части на последните и използваме закона за премахване на двойните отрицания.

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

Тъй като за едни и същи логически стойности x и y формулите са верни https://pandia.ru/text/78/396/images/image018.gif" width="124" height="21">. Следователно, в в този случай и двете части на еквивалентността имат една и съща истинска стойност.

Нека сега x и y имат различни логически стойности. Тогава еквивалентността и едно от двете импликации или ще бъдат неверни. Но в същото време връзката също ще бъде невярна. .

Така в този случай и двете части на еквивалентността имат едно и също логическо значение.

Еквивалентности 2 и 4 се доказват по подобен начин.

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

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

Има обаче операции, чрез които може да се изрази всяка от петте логически операции, които използваме. Такава операция е например операцията "Инсулт на Шефер". Тази операция се обозначава със символа ½ наляво " style="border-collapse:collapse;border:none;margin-left:6.75pt;margin-right: 6.75pt">

Съвременните компютри, базирани на "древни" електронни компютри, се основават на определени постулати като основни принципи на работа. Те се наричат закони на алгебрата на логиката. За първи път такава дисциплина е описана (разбира се, не толкова подробно, колкото в съвременния й вид) от древногръцкия учен Аристотел.

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

За да разберем по-добре темата, ще анализираме понятията, които ще помогнат в бъдеще да научим законите на алгебрата на логиката.

Може би основният термин в изучаваната дисциплина е изявление. Това е твърдение, което не може да бъде едновременно невярно и вярно. Той винаги притежава само една от тези характеристики. В същото време е конвенционално прието да се даде стойност 1 на истината, 0 на лъжата и да се нарече самото твърдение някакъв вид A, B, C. С други думи, формулата A=1 означава, че твърдението A е вярно. Изразите могат да се обработват по различни начини. Нека разгледаме накратко действията, които могат да се извършват с тях. Обърнете внимание също, че законите на алгебрата на логиката не могат да бъдат усвоени без познаване на тези правила.

1. Дизюнкциядве твърдения - резултат от операцията "или". Тя може да бъде или невярна, или вярна. Използва се знакът "v".

2. Съюз.Резултатът от такова действие, извършено с две пропозиции, ще бъде нов само ако и двете първоначални пропозиции са верни. Използва се операцията "и", символът "^".

3. Внушение.Операция "Ако А, тогава Б". Резултатът е твърдение, което е невярно само ако A е вярно и B е невярно. Използва се символът "->".

4. Еквивалентност.Операция "А ако и само ако B когато". Това твърдение е вярно, ако и двете променливи имат една и съща стойност. Символът "<->».

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

Сега нека разгледаме по-отблизо основните закони на алгебрата на логиката:

1. Комутативни или комутативни гласи, че промяната на местата на логически термини в операциите на конюнкция или дизюнкция не влияе на резултата.

2. Асоциативен или асоциативен. Съгласно този закон променливите в операциите на конюнкция или дизюнкция могат да се комбинират в групи.

3. Разпределение или разпространение. Същността на закона е, че същите променливи в уравненията могат да бъдат извадени от скоби, без да се променя логиката.

4. Закон на Де Морган (инверсия или отрицание). Отрицанието на операцията конюнкция е еквивалентно на дизюнкцията на отрицанието на оригиналните променливи. Отрицанието на дизюнкцията от своя страна е равно на конюнкцията на отрицанието на същите променливи.

5. Двойно отрицание. Отрицанието на дадено твърдение два пъти води до първоначалното твърдение, три пъти - неговото отрицание.

6. Законът за идемпотентността изглежда така за логическо събиране: x v x v x v x = x; за умножение: x^x^x^=x.

7. Законът за непротиворечивостта гласи: две твърдения, ако са противоречиви, не могат да бъдат верни едновременно.

8. Законът за изключването на третото. Сред две противоречиви твърдения едното винаги е вярно, другото е невярно, третото не е дадено.

9. Законът за поглъщане може да бъде написан по следния начин за логическо събиране: x v (x ^ y) = x, за умножение: x ^ (x v y) = x.

10. Законът за залепването. Две съседни връзки могат да се слепят, за да образуват връзка от по-нисък ранг. В този случай променливата, чрез която са били слепени оригиналните връзки, изчезва. Пример за логическо добавяне:

(x^y) v (-x^y)=y.

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

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

Закони на пропозиционалната алгебра

Закони на пропозиционалната алгебра (алгебра на логиката) са тавтологии.

Понякога тези закони се наричат теореми.

Първите четири от следните закони са основните закони на пропозиционалната алгебра.

Закон за идентичността:

А=А

Всяка концепция и преценка са идентични на себе си.

Например разсъждението Правилно казва, че езикът ще ви отведе в Киев, но вчера купих опушен език, което означава, че сега мога спокойно да отида в Киев неправилно, тъй като първата и втората дума „език“ означават различни понятия.

В разсъжденията: Движението е вечно. Ходенето на училище е движение. Следователно, отивайки на училище завинаги, думата „движение“ се използва в два различни смисъла (първият – във философския смисъл – като атрибут на материята, вторият – в обикновения смисъл – като действие за движение в пространството), което води до невярно заключение.

Закон за непротиворечивостта :

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

1. Числото 12345 е четно или нечетно, третото не е дадено.

2. Фирмата работи на загуба или на нула.

3. Тази течност може да е или да не е киселина.

Законът за изключената среда не е закон, признат от всички логици като универсален закон на логиката. Този закон се прилага, когато познанието се занимава с твърда ситуация: "или-или", "вярно-невярно". Когато има несигурност (например при разсъждения за бъдещето), законът на изключената среда често не може да бъде приложен.

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

Парадоксът (на гръцки paradoxos - неочакван, странен) в този пример произтича от факта, че изречението се отнася за себе си. Друг известен парадокс е проблемът с бръснаря: в един град бръснарят подстригва всички жители, с изключение на тези, които се подстригват сами. Кой подстригва бръснаря? В логиката, поради своята формалност, не е възможно да се получи формата на такова самореферентно твърдение. Това още веднъж потвърждава идеята, че с помощта на алгебрата на логиката е невъзможно да се изразят всички възможни мисли и аргументи. Нека покажем как въз основа на дефиницията на пропозиционалната еквивалентност могат да бъдат получени останалите закони на пропозиционалната алгебра.

Например, нека определим какво е еквивалентно (еквивалентно) A (двойно отрицание A, т.е. отрицание на отрицанието A).За да направим това, ще изградим таблица на истината:

По дефиниция на еквивалентност трябва да намерим колоната, чиито стойности съответстват на стойностите на колона A. Това ще бъде колона A.

Така можем да формулираме закона за двойното отрицание:

Ако отхвърлим дадено твърдение два пъти, тогава резултатът е оригиналното твърдение. Например изявлението A = Matroskin - кате еквивалентен на А = Не е вярно, че Матроскин не е котка.

По подобен начин могат да бъдат извлечени и проверени следните закони:

Постоянни свойства:

Закони на идемпотентността:

Колкото и пъти да повтаряме: телевизорът е включен или телевизорът е включен или телевизорът е включен... смисълът на твърдението няма да се промени. По същия начин от повторение топло е навън, топло е навън, ... няма да стане и градус по-топло.

Законите на комутативността:

A v B = B v A

A & B = B & A

Операндите A и B в операциите дизюнкция и конюнкция могат да бъдат разменени.

Закони за асоциативност:

A v(B v C) = (A v B) v C;

A & (B & C) = (A & B) & C.

Закони за разпределение:

A v (B & C) = (A v B) & (A v C)

(разпределителна дизюнкция
относно връзката)

A & (B v C) = (A & B) v (A & C)

(дистрибутивност на връзката
относно дизюнкция)

Закони за абсорбция:

A v (A & B) = A

A & (A v B) = A

Извършете доказателството на законите за поглъщане сами.

Законите на Де Морган:

Словесни формулировки на законите на де Морган:

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

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

1) Твърдението Не е вярно, че знам арабски или китайски е идентично с твърдението Не знам арабски и не знам китайски.

2) Твърдението Не е вярно, че научих урока и получих двойка за това е идентично с твърдението Или не научих урока, или не получих двойка за това.

Замяна на импликация и операции за еквивалентност

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

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

Помислете за следния пример.

Нека бъде дадено изявлението:

E = Не е вярно, че ако спечеля състезанието, ще получа награда.

Позволявам A = Аз ще спечеля състезанието,

B = Ще получа награда.

Тогава

Оттук, E = Ще спечеля състезанието, но няма да получа награда.