Алгебра на твърденията. Булеви операции

Планирайте

Твърдения с външно отрицание.

конюнктивни твърдения.

дизюнктивни твърдения.

Строго дизюнктивни твърдения.

Твърдения за еквивалентност.

Имплицитни твърдения.

Твърдения с външно отрицание.

Изявление с външно отрицание е изявление (съждение), в което се потвърждава липсата на определена ситуация. Най-често се изразява в изречение, което започва с фразата „не е вярно, че...“ или „не е вярно, че...“. Външното отрицание се обозначава със символа „ù“, наречен знак за отрицание. Този знак се определя от следната таблица на истината:

В твърдения с външно отрицание се отрича ситуацията в А. Например, ако А: „Волга се влива в Черно море“, тогава ùA: „Не е вярно, че Волга се влива в Черно море“.

конюнктивни твърдения.

Съединителните твърдения са тези, в които се потвърждава едновременното съществуване на две ситуации. Съединителните изявления се образуват от две изявления с помощта на съюзите „и“, „а“, „но“. Форма на съчинително сказуемо: (А&Б). Всяко от твърденията A и B може да приеме както стойността „true“, така и стойността „false“. Тези стойности са обозначени за краткост с буквите I л. Таблицата на истината за конюнктивните твърдения е следната:

В конюнктивните твърдения се посочва, че ситуацията, описана в А и В, се случва едновременно. Примери за съединителни твърдения: „Земята е планета, а Луната е спътник“; „Петров владееше добре логиката, но Сидоров – зле“; „Навън е тъмно и светлините в залата светят“; „Петров даде на длъжностното лице подкуп в брой, а Сидоров му даде бутилка.

дизюнктивни твърдения.

Дизюнктивните твърдения са твърдения, които твърдят съществуването на поне една от двете ситуации, описани в А и Б. Дизюнкцията се обозначава със символа V и се изразява на естествен език чрез съюза „или“.

Табличната дефиниция на знака за дизюнкция е както следва:

Пример за разделително изявление: "Роман Сергеевич Иванов е учител или Роман Сергеевич Иванов е завършил студент."

Строго дизюнктивни твърдения.

Строго дизюнктивните твърдения са твърдения, които твърдят съществуването на точно една от двете ситуации, описани в А и Б. Такива твърдения най-често се извършват с помощта на изречения със съюза „или ..., или ...“ („или ..., или ...”). Строгата дизюнкция се обозначава със символа V* (чете се „или... или...“).

Табличната дефиниция на знака за строга дизюнкция е следната:

Пример за строго разделително твърдение: "Или навън е слънчево, или вали."

Стойност на истината

Тази статия или раздел е груб превод на статия на друг език (вижте Проверка на преводите). Може да е генериран от програма за превод или от някой с малко познания по оригиналния език. ¬( Образец:Mvar∧Образец:Mvar) ⇔ ¬Образец:Mvar ∨ ¬Образец:Mvar ¬( Образец:Mvar∨Образец:Mvar) ⇔ ¬Образец:Mvar ∧ ¬Образец:Mvar Многозначна логика Многозначна логика (например размитата логика позволява повече от две стойности на истината, евентуално съдържащи някои вътрешни структури. Алгебрична семантика Не всички логически системи са истински ценностни системи в смисъл, че логическите връзки могат да се тълкуват като истинност на функциите. Например на интуиционистката логика липсва пълен набор от стойности на истината, тъй като нейната семантика е дефинирана от гледна точка на доказуемостта на условието, а не директно от гледна точка на задължителната валидност на формулите. В други теории Интуиционистичната теория на типа използва типове вместо стойности на истината. Теорията на топоса използва стойностите на истината в специален смисъл: стойността на истината на топоса е глобалният елемент x подобект на класификатора. Притежаването на ценността на истината в този смисъл няма ценностната логика на истината. Вижте също Връзки Фондация Уикимедия. 2010 г. Вижте каква е "стойността на истината" в други речници: Съдържание, обозначено от един или друг езиков израз чрез дума, изречение, знак и др. Въпросът за З. на езиковите изрази се изучава от лингвистиката, семиотиката и логическата семантика. Разграничете предмет, семантичен и изразителен Z. езиков ... Философска енциклопедия Стойността на истината (в логиката), стойността, която твърдението (изречението, преценката) приема, разглеждано във връзка със съдържанието, показано в него. В обикновената (класическата) логика две I. z. "вярно невярно"; в…… Велика съветска енциклопедия Таблицата на истината е таблица, която описва логическа функция. Под "логическа функция" в този случай се разбира функция, в която стойностите на променливите (функционални параметри) и стойността на самата функция изразяват логическа истина. ... ... Wikipedia Таблица, която установява стойността на истината на съставен израз, дадена на стойностите на неговите прости изрази. В класическата математическа логика се приема, че всяко просто число (което не съдържа логически ... ... Речник на логическите термини Денотатум (от лат. denotatum обозначен), термин от лингвистиката и екстензионалната логика, обозначаващ 1) разширение, 2) десигнат, 3) референт и 4) семантично ядро ​​на значението. Съдържание 1 Обозначение като разширение 2 Обозначаване като обозначение ... Wikipedia Една от възможните характеристики на изявлението по отношение на съответствието му с описания фрагмент от реалността. Ако се приеме, че всяко твърдение е вярно или невярно (т.е. че е или вярно ... Речник на логическите термини Набор от логически системи, основани на принципа на многозначността. В класическата двузначна логика изразите приемат само две стойности „истина“ и „лъжа“ по време на интерпретация, в M.l. други стойности също се вземат предвид, например. "за неопределено време" ...... Философска енциклопедия - (от лат. factum направено, извършено) 1) синоним на понятията "истина", "събитие", "резултат"; нещо реално за разлика от измисленото; конкретно, единично за разлика от абстрактното и общото; 2) във философията на науката от специален вид p ... Философска енциклопедия - (in logistic) - истинността на изречението (съждението, твърдението), дължима, за разлика от т.нар. логично истина, съдържанието на това изречение. С други думи, едно изречение е действително вярно, когато неговата истинност зависи от стойностите... Философска енциклопедия Стереометрична семантика- тълкуването на логиката като наука за получаване на истински следствия от истински предпоставки все повече отстъпва място на по-широка концепция, свързана или с обобщаване на концепцията за следване, базирана на традиционна оценка на истината и на практическа ... ... Проективен философски речник Книги Как искрено да вярваме в Бог, или единственото, което има значение за развитието на вярата, Вражев В. среда с...

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

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

Фигурата по-горе е илюстрация на феномен, известен като парадокса на лъжеца. В същото време, според автора на проекта, подобни парадокси са възможни само в среда, която не е свободна от политически проблеми, където някой може да бъде обявен за лъжец a priori. В естествения пластов свят на темата "истина" или "лъжа" се оценява само поотделно взети твърдения . И по-късно в този урок ще ви запознаем с възможност за оценка на много твърдения по тази тема (и след това вижте правилните отговори). Включително сложни твърдения, в които по-простите са свързани помежду си със знаци на логически операции. Но нека първо разгледаме тези операции върху самите предложения.

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

И така, може да се декларира логическа променлива с име "UserRegistered" (или неин английски еквивалент), имаща формата на изявление, на което може да бъде присвоена логическата стойност "true", ако са изпълнени условията, че данните за регистрация са изпратени от потребителя и тези данни се разпознават от програмата като валидни. При по-нататъшни изчисления стойностите на променливите могат да се променят в зависимост от това каква логическа стойност („true“ или „false“) има променливата „UserLogged in“. В други случаи на променлива, например с име „Повече от три дни до деня“, може да бъде присвоена стойност „Истина“ до определен блок от изчисления и по време на по-нататъшното изпълнение на програмата тази стойност може да бъде се запазва или променя на "false" и ходът на по-нататъшното изпълнение зависи от стойността на тази променлива програми.

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

Логически операции върху изрази

За математически твърдения човек винаги може да избира между две различни алтернативи „вярно“ и „невярно“, но за твърдения, направени на „вербален“ език, понятията „вярно“ и „невярно“ са малко по-неясни. Въпреки това, например, такива вербални форми като „Върви си вкъщи“ и „Вали ли?“ не са изказвания. Следователно е ясно, че изказванията са словесни форми, в които се заявява нещо . Въпросителни или възклицателни изречения, призиви, както и пожелания или искания не са твърдения. Те не могат да бъдат оценени със стойностите "true" и "false".

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

Дадени са например преценки: „кучето е животно“, „Париж е столицата на Италия“, „3

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

Тези връзки правят възможно, чрез комбиниране на различни твърдения, да се формират нови твърдения - сложни твърдения . Например, куп "и". Нека бъдат дадени изявленията: π по-голямо от 3" и твърдението " π по-малко от 4. Можете да организирате нов - сложен отчет " π повече от 3 и π по-малко от 4". Твърдението "ако π ирационално тогава π ² също е ирационално" се получава чрез свързване на две изявления с връзката "ако - тогава". И накрая, можем да получим ново - сложно изявление - от всяко изявление - отричащо оригиналното изявление.

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

Нека са дадени две произволни твърдения Аи б.

1 . Първата логическа операция върху тези твърдения - конюнкция - е образуването на ново твърдение, което ще обозначим А ∧ би което е вярно тогава и само ако Аи бвярно. В обикновената реч тази операция съответства на връзката на твърдения с куп "и".

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

А	б	А ∧ б
И	И	И
И	Л	Л
Л	И	Л
Л	Л	Л

2 . Втората логическа операция върху изрази Аи б- дизюнкция, изразена като А ∨ б, се определя по следния начин: вярно е тогава и само ако поне едно от първоначалните твърдения е вярно. В обикновената реч тази операция съответства на свързването на твърдения с куп "или". Тук обаче имаме неразделително "или", което се разбира в смисъла на "или-или", когато Аи би двете не могат да бъдат верни. В дефиницията на пропозиционалната логика А ∨ бвярно, ако само едно от твърденията е вярно и ако и двете твърдения са верни Аи б.

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

А	б	А ∨ б
И	И	И
И	Л	И
Л	И	И
Л	Л	Л

3 . Третата логическа операция върху твърдения Аи б, изразено като А → б; полученото твърдение е невярно тогава и само ако Авярно и бневярно. АНаречен колет , б - следствие , и изявлението А → б - следното , наричано още импликация. В обикновената реч тази операция съответства на връзката "ако - тогава": "ако А, тогава б". Но в дефиницията на пропозиционалната логика това твърдение винаги е вярно, независимо дали предложението е вярно или невярно б. Това обстоятелство може да се формулира накратко по следния начин: „всичко, което искате, произтича от фалшивото“. На свой ред, ако Авярно и бневярно, тогава цялото твърдение А → бневярно. Ще бъде вярно тогава и само тогава А, и бвярно. Накратко това може да се формулира по следния начин: „лъжата не може да следва от истината“.

Таблица на истината, която да следвате (внушение):

А	б	А → б
И	И	И
И	Л	Л
Л	И	И
Л	Л	И

4 . Четвъртата логическа операция върху твърдения, по-точно върху едно твърдение, се нарича отрицание на твърдение. Аи се означава с ~ А(можете също да намерите използването не на символа ~, а на символа ¬, както и надчертаната линия А). ~ Аима твърдение, което е невярно, когато Авярно и вярно кога Аневярно.

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

А	~ А
Л	И
И	Л

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

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

А	б	А → б	б → А	А ↔ б
И	И	И	И	И
И	Л	Л	И	Л
Л	И	И	Л	Л
Л	Л	И	И	И

Повечето езици за програмиране имат специални символи за логически стойности на предложенията, те са написани на почти всички езици като true (вярно) и false (false).

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

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

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

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

Пример 1

1) (2 = 2) И (7 = 7) ;

2) Не(15;

3) ("Бор" = "Дъб") ИЛИ ("Череша" = "Клен");

4) Not("Pine" = "Oak") ;

5) (Не(15 20) ;

6) („На очите е дадено да виждат“) и („Под третия етаж е вторият етаж“);

7) (6/2 = 3) ИЛИ (7*5 = 20) .

1) Стойността на твърдението в първите скоби е "вярно", стойността на израза във вторите скоби също е вярно. И двата израза са свързани чрез логическата операция "И" (вижте правилата за тази операция по-горе), така че логическата стойност на целия този оператор е "истина".

2) Значението на твърдението в скоби е „невярно“. Това твърдение е предшествано от операция за логическо отрицание, така че логическата стойност на цялото това твърдение е "истина".

3) Значението на твърдението в първите скоби е „невярно“, значението на твърдението във вторите скоби също е „невярно“. Изявленията са свързани с логическата операция "ИЛИ" и нито едно от изявленията няма стойност "true". Следователно логичният смисъл на цялото това твърдение е „лъжа“.

4) Значението на твърдението в скоби е „невярно“. Това твърдение се предшества от операция за логическо отрицание. Следователно логическият смисъл на цялото дадено твърдение е "вярно".

5) В първите скоби твърдението във вътрешните скоби се отрича. Това твърдение в скоби дава оценка на "невярно", така че неговото отрицание ще се изчисли на логическата стойност "вярно". Твърдението във вторите скоби има стойност „лъжа“. Тези две твърдения са свързани с логическата операция "И", тоест получава се "вярно И невярно". Следователно логическият смисъл на цялото дадено твърдение е „лъжа“.

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

7) Значението на твърдението в първите скоби е "вярно". Значението на твърдението във вторите скоби е „невярно“. Тези две твърдения са свързани с логическата операция "ИЛИ", тоест получава се "вярно ИЛИ невярно". Следователно логическият смисъл на цялото дадено твърдение е "вярно".

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

1) „Потребителят не е регистриран“;

2) „Днес е неделя и някои служители са на работа“;

3) „Потребителят се регистрира, когато и само когато данните, изпратени от потребителя, се окажат валидни.“

1) стр- единичен оператор "Потребителят е регистриран", логическа операция: ;

2) стр- единично изявление "Днес е неделя", р- "Някои служители са на работа", логическа операция: ;

3) стр- единично изявление "Потребителят е регистриран", р- "Изпратените от потребителя данни са валидни", логическа операция: .

Решете сами примери с пропозиционална логика и след това разгледайте решенията

Пример 3Изчислете булевите стойности на следните изрази:

1) („В една минута има 70 секунди“) ИЛИ („Въртящ се часовник показва времето“);

2) (28 > 7) И (300/5 = 60) ;

3) ("Телевизор - електроуред") и ("Стъкло - дърво");

4) Не ((300 > 100) ИЛИ ("Жаждата може да се утоли с вода"));

5) (75 < 81) → (88 = 88) .

Пример 4Запишете следните сложни твърдения с помощта на логически операции и изчислете техните логически стойности:

1) „Ако часовникът не показва правилно времето, тогава можете да дойдете в клас в грешно време“;

2) „В огледалото можете да видите отражението си и Париж – столицата на САЩ“;

Пример 5Определете булев израз

(стр → р) ↔ (r → с) ,

стр = "278 > 5" ,

р= "Ябълка = портокал",

стр = "0 = 9" ,

с= "Шапката покрива главата".

Формули на пропозиционалната логика

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

В примери 1 и 2 научихме как да пишем сложни изрази с помощта на логически операции. Всъщност те се наричат ​​формули на пропозиционалната логика.

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

стр, р, r, ..., стр 1 , р 1 , r 1 , ...

Тези букви ще играят ролята на променливи, които приемат стойностите на истината „true“ и „false“ като стойности. Тези променливи се наричат ​​още пропозиционални променливи. Оттук нататък ще ги наричаме елементарни формули или атоми .

За да се конструират пропозиционални логически формули, в допълнение към горните букви се използват знаците на логическите операции

~, ∧, ∨, →, ↔,

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

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

1) елементарните формули (атоми) са формули на пропозиционалната логика;

2) ако Аи б- формули на пропозиционална логика, след това ~ А , (А ∧ б) , (А ∨ б) , (А → б) , (А ↔ б) също са формули на пропозиционалната логика;

3) само онези изрази са формули на пропозиционална логика, за които това следва от 1) и 2).

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

Пример 6Позволявам стр- единично твърдение (атом) "Всички рационални числа са реални", р- "Някои реални числа са рационални числа", r- "някои рационални числа са реални". Преведете под формата на словесни предложения следните формули на пропозиционалната логика:

6) .

1) "няма реални числа, които да са рационални";

2) "ако не всички рационални числа са реални, тогава няма рационални числа, които да са реални";

3) „ако всички рационални числа са реални, то някои реални числа са рационални числа и някои рационални числа са реални“;

4) „всички реални числа са рационални числа и някои реални числа са рационални числа, а някои рационални числа са реални числа“;

5) „всички рационални числа са реални тогава и само ако не е така, че не всички рационални числа са реални“;

6) "не е така, че не е така, че не всички рационални числа са реални и няма реални числа, които са рационални, или няма рационални числа, които са реални."

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

Решение. Започваме да компилираме таблицата на истината, като записваме стойностите („true“ или „false“) за единични твърдения (атоми) стр , ри r. Всички възможни стойности са записани в осем реда на таблицата. Освен това, когато определяте стойностите на операцията за импликация и се движите надясно в таблицата, не забравяйте, че стойността е равна на "false", когато "true" предполага "false".

стр	р	r					f
И	И	И	И	И	И	И	И
И	И	Л	И	И	И	Л	И
И	Л	И	И	Л	Л	Л	Л
И	Л	Л	И	Л	Л	И	И
Л	И	И	Л	И	Л	И	И
Л	И	Л	Л	И	Л	И	Л
Л	Л	И	И	И	И	И	И
Л	Л	Л	И	И	И	Л	И

Обърнете внимание, че нито един атом няма формата ~ А , (А ∧ б) , (А ∨ б) , (А → б) , (А ↔ б) . Това са сложни формули.

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

1) в сложна формула ще пропуснем външната двойка скоби;

2) подредете знаците на логическите операции "по старшинство":

↔, →, ∨, ∧, ~ .

В този списък знакът ↔ има най-голям обхват, а знакът ~ има най-малък обхват. Обхватът на знака за операция се разбира като онези части от пропозиционалната логическа формула, към които се прилага разглежданото появяване на този знак (върху които той действа). По този начин във всяка формула е възможно да се пропуснат тези двойки скоби, които могат да бъдат възстановени, като се вземе предвид "редът на приоритета". И когато се възстановяват скоби, първо се поставят всички скоби, които се отнасят за всички появявания на знака ~ (в този случай се движим отляво надясно), след това за всички появявания на знака ∧ и т.н.

Пример 8Възстановете скобите във формулата на пропозиционалната логика б ↔ ~ ° С ∨ д ∧ А .

Решение. Скобите се възстановяват стъпка по стъпка, както следва:

б ↔ (~ ° С) ∨ д ∧ А

б ↔ (~ ° С) ∨ (д ∧ А)

б ↔ ((~ ° С) ∨ (д ∧ А))

(б ↔ ((~ ° С) ∨ (д ∧ А)))

Не всяка формула на пропозиционалната логика може да бъде написана без скоби. Например във формули НО → (б → ° С) и ~( А → б) не е възможно по-нататъшно изтриване на скоби.

Тавтологии и противоречия

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

Тъй като истинността или неверността на сложните твърдения зависи само от значенията, а не от съдържанието на твърденията, всяко от които отговаря на определена буква, тогава тестът дали дадено твърдение е тавтология може да бъде заменен по следния начин. В изследвания израз стойностите 1 и 0 (съответно "true" и "false") се заместват с буквите по всички възможни начини и с помощта на логически операции се изчисляват логическите стойности на изразите. Ако всички тези стойности са равни на 1, тогава изследваният израз е тавтология и ако поне едно заместване дава 0, тогава това не е тавтология.

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

Обратното значение е логическо противоречие. Ако всички стойности на предложението са 0, тогава изразът е логическо противоречие.

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

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

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

Решение. Правим таблица на истината:

И	И	И	И	И
И	Л	Л	Л	И
Л	И	Л	И	И
Л	Л	Л	Л	И

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

Тема на програмата: Изявления и операции върху тях.

Цели на урока:

1) Обобщете теоретичните знания по темата: "Изявления и операции върху тях."

2) Обмислете алгоритми за решаване на задачи по темата „Изявления и операции върху тях“, решавайте проблеми.

3) Да се ​​​​формира способността за прогнозиране на собствената дейност, способността да организира дейността си и да я анализира.

Преднина:Един час.

Теоретична основа

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

Примери за изрази.
1) Москва стои на Нева.
2) Лондон е столицата на Англия.
3) Соколът не е риба.
4) Числото 6 се дели на 2 и 3.
Твърдения 2), 3), 4) са верни, а твърдение 1) е невярно.
Очевидно изречението „Да живее Русия!“ не е твърдение.
Има два вида изявления.
Едно твърдение, което е единично твърдение, обикновено се нарича просто или елементарно. Примери за елементарни твърдения са твърдения 1) и 2).
Твърдения, които се получават от елементарни с помощта на граматични връзки „не“, „и“, „или“, „ако .... тогава ...“, „тогава и само тогава“, обикновено се наричат ​​сложни или съставни .
И така, твърдението 3) се получава от простото твърдение „Соколът е риба“ с помощта на отрицанието на „не“, твърдението 4) се формира от елементарните твърдения „Числото 6 се дели на 2“, „Числото 6 се дели на 3“, свързано със съюза „и“.
По същия начин сложни твърдения могат да бъдат получени от прости твърдения, използващи граматичните връзки "или", "ако и само тогава".
В алгебрата на логиката всички твърдения се разглеждат само от гледна точка на техния логически смисъл, а тяхното светско съдържание се абстрахира. Смята се, че всяко твърдение е вярно или невярно и нито едно твърдение не може да бъде едновременно вярно и невярно.
Елементарните твърдения са обозначени с малки букви от латинската азбука: x, y, z, ..., a, b, c, ...;истинската стойност на твърдението е числото 1, а грешната стойност е буквеното число 0.
Ако твърдението авярно, ще пишем а = 1, какво ако аневярно, тогава а = 0.

Логически операции върху изрази

Отрицание.

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

Отказ от изявление хотбелязани и прочетени "не X"или "не е вярно, че х".

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

Таблици от този вид се наричат ​​таблици на истината.
Позволявам хизявление. Тъй като това също е изявление, възможно е да се формира отрицанието на изявлението, тоест изявлението, което се нарича двойно отрицание на изявлението х. Ясно е, че логическите значения на твърденията хи мач.

Например, за твърдението „Путин е президент на Русия“, отрицателното ще бъде твърдението „Путин не е президент на Русия“, а двойното отрицание ще бъде твърдението „Не е вярно, че Путин не е президент на Русия“.

Съчетание.

Конюнкция (логическо умножение) на две твърдения x и yизвиква се ново твърдение, което се счита за вярно, ако и двете предложения x и yвярно и невярно, ако поне едно от тях е невярно.
връзка на предложенията x и yобозначен със символа x&y ( , xy), Прочети "x и y". поговорки x и yсе наричат ​​членове на връзката.
Логическите стойности на връзката са описани от следната таблица на истината:

Например за твърденията „6 се дели на 2“, „6 се дели на 3“, тяхната конюнкция ще бъде твърдението „6 се дели на 2 и 6 се дели на 3“, което очевидно е вярно.

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

Дизюнкция

Дизюнкция (логическо събиране) на две твърдения x и yизвиква се ново предложение, което се счита за вярно, ако поне едно от предложенията x, y true и false, ако и двете са false. Дизюнкция на предложенията x, yобозначен със символа "x V y", Прочети "x или y". поговорки x, yсе наричат ​​членове на дизюнкцията.
Логическите стойности на дизюнкцията са описани от следната таблица на истината:

В ежедневната реч съюзът "или" се използва в различен смисъл: изключителен и неизключителен. В алгебрата на логиката съюзът "или" винаги се използва в неизключителен смисъл.

Внушение.

Импликация на две твърдения x и yИзвиква се ново предложение, което е невярно, ако x е вярно и y е невярно, и вярно във всички останали случаи.
Внушение на твърдения x, yобозначен със символа , Прочети „ако x, то y“ или „от x следва y“.изявление хнаречено условие или предпоставка, твърдение при- следствие или заключение, твърдение следване или импликация.

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

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

Еквивалентност.

Еквивалентност на две твърдения x и yизвиква се ново предложение, което се счита за вярно, когато и двете предложения x, yили едновременно вярно или и двете невярно, и невярно във всички останали случаи.

Еквивалентност на твърдението x, yобозначен със символа, четете „за да има x, е необходимо и достатъчно y“ или „x тогава и само ако y“.поговорки x, yсе наричат ​​условия на еквивалентност.
Логическите стойности на операцията за еквивалентност са описани от следната таблица на истината:

Еквивалентността играе важна роля в математическите доказателства. Известно е, че значителен брой теореми са формулирани под формата на необходими и достатъчни условия, тоест под формата на еквивалентност. В този случай, знаейки истинността или неистинността на един от двата термина за еквивалентност и доказвайки истинността на самата еквивалентност, ние заключаваме, че вторият термин за еквивалентност е верен или неверен.

Практически задачи

1. Установете логическата структура на следните изречения и ги запишете на езика на пропозиционалната логика:

• Ако металът се нагрее, той се топи.
• Не е вярно, че философските спорове са неразрешими.
• Парите са продукт на спонтанното развитие на стоковите отношения, а не резултат от споразумение или друг съзнателен акт.

2. Запишете следните твърдения в логическа формула:

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

Б) ако - правоъгълен и страните са равни, то

3. Проверете истинността на твърдението:

какво ако, .

б) ако, .

в) ако, .

4. Проверете истинността на твърдението:

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

б) Ще отида или на кино, или на басейн. Ако отида на кино, ще получа естетическо удоволствие. Ако отида на басейн, ще получа физическо удоволствие. Следователно, ако получа физическо удоволствие, няма да получа естетическо.

5. На въпроса: „Кой от тримата студенти е учил дискретна математика?“ е получен правилният отговор: „Ако е учил първото, значи е учил третото, но не е вярно, че ако е учил второто, значи е учил третото“. Кой е учил дискретна математика?

6. Определете кой от четиримата студенти е издържал изпита, ако е известно:

мина ли първото, мина и второто;

ако второто мина, значи третото мина или първото не мина;

ако четвъртият не мине, значи първият мина, а третият не мина;

ако четвъртият мина, значи първият мина.

тестови въпроси

1. Какви елементи са включени в езика на логиката?

2. Какви начини за установяване на валидността на логическа формула познавате?

Библиография

Упражнение #10-11

Тема на програмата: Формули на пропозиционалната алгебра.

Имоти

Помислете за няколко свойства на декартовия продукт:

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

2. Броят на елементите в декартовото произведение е равен на произведението на броя на елементите на множителните множества (ако са крайни, разбира се): | А× б|=|А|⋅|б| .

3. A np ≠(A n) стр- в първия случай е препоръчително резултатът от декартовия продукт да се разглежда като матрица с размери 1 × np, във втория - като матрица от размери н× стр .

4. Комутативният закон не е изпълнен, т.к двойките елементи на резултата от декартовия продукт са подредени: А× б≠б× А .

5. Законът за сдружаване не е изпълнен: ( А× б)× ° С≠А×( б× ° С) .

6. Има дистрибутивност по отношение на основните операции върху множества: ( А∗б)× ° С=(А× ° С)∗(б× ° С),∗∈{∩,∪,∖}

11. Понятие за изказване. Елементарни и съставни твърдения.

изявлениее твърдение или декларативно изречение, за което може да се каже, че е вярно (T-1) или невярно (L-0), но не и двете едновременно.

Например „Днес вали“, „Иванов завърши лабораторна работа № 2 по физика“.

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

Въпреки че изявление като „Днес не е четвъртък“ не е съставено от две различни прости изявления, за еднаквост на конструкцията то също се счита за съставно, тъй като стойността му на истинност се определя от стойността на истината на друго изявление „Днес е четвъртък "

Пример 2Следните изявления се третират като съставни изявления:

Чета Московски комсомолец и Комерсант.

Щом го е казал, значи е истина.

Слънцето не е звезда.

Ако е слънчево и температурата надвишава 25 0, ще пристигна с влак или кола

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

12. Операции върху извлечения.

1. операция за отрицание.

Отрицанието на твърдението НО (чете „не НО"," това не е вярно НО“), което е вярно, когато НОневярно и невярно кога НО- вярно.

Отрицателни твърдения НОи Наречен противоположност.

2. операция на свързване.

съчетаниеизявления НОи ATсе нарича изявление А Б(Прочети " НОи AT“), чиито истински значения се определят тогава и само ако и двете твърдения НОи ATвярно.

Конюнкцията на предложенията се нарича логически продукт и често се обозначава AB.

Нека изявлението НО– „през март температурата на въздуха от 0 Сдо + 7 C» и казвайки AT– „Във Витебск вали“. Тогава А Бще бъде както следва: „през март температурата на въздуха от 0 Сдо + 7 Cа във Витебск вали." Тази връзка ще бъде вярна, ако има твърдения НОи ATвярно. Ако се окаже, че температурата е била по-ниска 0 Сили тогава във Витебск нямаше дъжд А Бще бъде невярно.

3 . операция на дизюнкция.

дизюнкцияизявления НОи ATсе нарича изявление А Б (НОили AT), което е вярно тогава и само ако поне едно от твърденията е вярно и невярно - когато и двете твърдения са неверни.

Дизюнкцията на предложенията се нарича още логическа сума A+B.

Изявлението " 4<5 или 4=5 ' истина е. Тъй като изявлението " 4<5 " е вярно и твърдението " 4=5 ' е невярно, тогава А Бе вярно твърдение 4 5 ».

4 . импликационна операция.

внушениеизявления НОи ATсе нарича изявление А Б("ако НО, тогава AT“, „от НОТрябва AT“), чиято стойност е невярна тогава и само ако НОвярно и ATневярно.

В импликацията А Бизявление НОНаречен основа,или изпращане и извлечението AT – следствие,или заключение.

13. Таблици на истинността на твърденията.

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

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

Изчисляване на истинността на сложни твърдения;

Установяване на еквивалентност на твърдения;

Дефиниции на тавтологиите.

Установяване на истинността на сложни твърдения.

Пример 1Определете истинността на твърдението C

Решение.Съставът на сложно изявление включва 3 прости изявления: A, B, C. Колоните в таблицата са попълнени със стойности (0, 1). Посочени са всички възможни ситуации. Простите изречения са разделени от сложните с двойна вертикална линия.
При съставянето на таблицата трябва да се внимава да не се обърка редът на действията; запълвайки колоните, трябва да се движите „отвътре навън“, т.е. от елементарни формули към все по-сложни; последната колона за попълване съдържа стойностите на оригиналната формула.

НО	AT	ОТ		A+		· ОТ

Таблицата показва, че това твърдение е вярно само ако A=0, B=1, C=1. Във всички останали случаи е невярно.

14. Еквивалентни формули.

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

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

За всякакви формули НО, AT, ОТеквивалентите са валидни.

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

закон на идемпотентността

1-вярно

0-невярно

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

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

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

формули за разделяне

облигационно право

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

закон на де Морган

III. Еквивалентности, изразяващи основните закони на алгебрата на логиката.

комутативно право

асоциативен закон

разпределителен закон

15. Формули на пропозиционалната логика.

Видове формули в класическата пропозиционална логика- в пропозиционалната логика се разграничават следните видове формули:

1. Закони(идентично верни формули) - формули, които за всяка интерпретация на пропозиционални променливи приемат стойността "вярно";

2. противоречия(идентично неверни формули) - формули, които за всяка интерпретация на пропозиционални променливи приемат стойността "фалшив";

3. Задоволителни формули- такива, които приемат значението "вярно"за поне един набор от истинностни стойности на пропозиционалните променливи, включени в тях.

Основни закони на класическата пропозиционална логика:

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

2. Законът на противоречието: ;

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

4. Законите на комутативността и: , ;

5. Законите за дистрибутивност са относителни към , и обратно: , ;

6. Законът за премахване на истинския член на връзката: ;

7. Законът за премахване на фалшивия член на дизюнкцията: ;

8. Закон за противопоставяне: ;

9. Закони за взаимна изразимост на пропозиционалните връзки: , , , , , .

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

16. Предикати и операции върху тях. Квантори.

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

В зависимост от броя на променливите, включени в предложението, се разграничават единични, двойни, тройни и др. предикатите, обозначени съответно: A( х), AT( х, при), ОТ( х, при, z).

Ако е даден някакъв предикат, тогава два набора са свързани с него:

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

2. Истинният набор T,състоящ се от всички тези стойности на променливите, при заместването им в предиката се получава вярно твърдение.

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

Можете да извършвате същите операции върху предикати, както и върху изрази.

1. Отричанепредикат A( х), дефиниран в множеството X, се нарича предикат верен за тези стойности, за които предикатът A( х) се превръща в невярно твърдение и обратно.

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

Множеството за истинност на предиката е допълнение към множеството за истинност на предиката A( х). Означаваме с T A истинностното множество на предиката A( х), а чрез T - истинностното множество на предиката . Тогава .

2. съчетаниепредикати A( х) и B( хх) AT( х х X, при което и двата предиката се превръщат в верни твърдения.

Истинното множество на конюнкцията от предикати е пресечната точка на истинните множества на предиката A( х) AT( х). Ако означим истинностното множество на предиката A(x) с T A, истинностното множество на предиката B(x) с T B и истинностното множество на предиката A(x) B(x) с , тогава

3. дизюнкцияпредикати A( Х)и B( х), дефиниран върху множеството X, се нарича предикат A( х) AT( х), което се превръща в истинско предложение за тези и само тези ценности х X, при което поне един от предикатите се превърна в вярно твърдение.

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

4.внушениепредикати A( х) и B( х), дефиниран върху множеството X, се нарича предикат A( х) AT( х), което е невярно за онези и само онези стойности на променливата, за които първият предикат става верен, а вторият става невярен.

Истинното множество на импликацията на предикатите е обединението на истинното множество на предиката B( х) с добавяне към набора за истинност на предиката A( х), т.е.

5. Еквивалентностпредикати A( х) и B( х), дефиниран в множеството X, се нарича предикат, който се превръща в вярно твърдение за всички онези и само онези стойности на променливата, за които и двата предиката се превръщат или в верни твърдения, или в неверни твърдения.

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

Кванторни операции върху предикати

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

За числата 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 можете да кажете: а) всичкодадените числа са прости; б) някоиот дадените числа са четни.

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

Ако премахнем думата „всички“ от изречение „а“ и думата „някои“ от изречение „б“, тогава получаваме следните предикати: „дадените числа са прости“, „дадените числа са нечетни“.

Думите "всички" и "някои" се наричат ​​квантори. Думата „квантор“ е от латински произход и означава „колко“, т.е. квантификаторът показва колко (всички или някои) обекти са споменати в дадено изречение.

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

Условия се наричат ​​"всеки", "всеки", "всеки". – универсален квантор.Определен .

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

В пример 1 за R1домейн на дефиниция: , набор от стойности - . За R2домейн на дефиниция: , набор от стойности: .

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

В първия случай две взаимно перпендикулярни линии са избрани като хоризонтална и вертикална ос. На хоризонталната ос положете елементите на комплекта Аи начертайте вертикална линия през всяка точка. На вертикалната ос положете елементите на комплекта бначертайте хоризонтална линия през всяка точка. Пресечните точки на хоризонталните и вертикалните линии изобразяват елементите на директния продукт

18. Методи за задаване на бинарни отношения.

Всяко подмножество на декартовото произведение A × B се нарича двоично отношение, дефинирано върху двойка множества A и B (на латински „bis“ означава „два пъти“). В общия случай, по аналогия с бинарните отношения, може също да се разглеждат n-арни отношения като подредени последователности от n елемента, взети от едно от n множества.

Символът R се използва за обозначаване на двоична релация.Тъй като R е подмножество на множеството A×B, можем да напишем R⊆A×. Ако се изисква да се посочи, че (a, b) ∈ R, т.е. има връзка R между елементите a ∈ A и b ∈ B, тогава напишете aRb.

Начини за уточняване на двоични отношения:

1. Това е използването на правилото, според което се посочват всички елементи, включени в това отношение. Вместо правило, можете да изброите елементите на дадено отношение, като ги изброите директно;

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

На (фигура 1.16) е показана координатната мрежа за комплекти. Пресечните точки на три вертикални прави с шест хоризонтални съответстват на елементите на множеството A×B. Кръгчетата върху решетката маркират елементите на релацията aRb, където a ∈ A и b ∈ B, R означава релацията “разделя”.

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

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

19. Рефлексивност на бинарно отношение. Пример.

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

Свойството на рефлексивност за дадени отношения от матрица се характеризира с факта, че всички диагонални елементи на матрицата са равни на 1; за дадени отношения от графиката, всеки елемент има цикъл - дъга (x, x).

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

Ако антирефлексивната връзка е дадена от матрица, тогава всички диагонални елементи са нула. Когато такава връзка е дадена от граф, всеки връх няма цикъл - няма дъги от формата (x, x).

Формално антирефлексивността на едно отношение се дефинира като: .

Ако условието за рефлексивност не е изпълнено за всички елементи на множеството, се казва, че връзката е нерефлексивна.

©2015-2019 сайт
Всички права принадлежат на техните автори. Този сайт не претендира за авторство, но предоставя безплатно използване.
Дата на създаване на страницата: 2016-04-12