Булева алгебра. Алгебра на логиката. Елементи на математическата логика

В днешния свят ние все по-често с помощта на различни машини и приспособления. И не само, когато е необходимо да се прилага буквално свръхчовешка сила: преместване на товара, за да го вдигне на височината, копаят дълъг и дълбок ров, и т.н. Автомобили днес събират роботи, храна се приготвя Multivarki и елементарни аритметични изчисления произвеждат калкулатори ... Все по-често чуваме изразът "Булева алгебра". Може би е дошло време да се разбере ролята на човека в създаването на роботи и машини способността за решаване не само математически, но логически задачи.

логика

Преведено от гръцки, логиката е организирана система на мислене, която създава отношения между дадените условия и ви позволява да правите изводи въз основа на предположения и допускания. Много често се питаме: "Логично ли е?" Отговорът отговаря на нашите допускания или критикува мисълта. Но процесът не спира: продължаваме да разсъждаваме.

Понякога броят на условията (уводно) е толкова голям и взаимоотношенията между тях са толкова объркващи и сложни, че човешкият мозък не може да "смила" всичко наведнъж. Може да отнеме повече от месец (седмица, година), за да разберете какво се случва. Но съвременният живот не ни дава такива времеви интервали за взимане на решения. И прибягваме до помощта на компютрите. И тук се появява алгебра на логиката със своите закони и свойства. След като изтеглихме всички първоначални данни, позволяваме на компютъра да разпознае всички взаимоотношения, да премахне противоречията и да намери задоволително решение.

Математика и логика

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

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

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

Джордж Буле

Самата личност на автора заслужава специално внимание. Дори и да се има предвид факта, че в миналото хората са станали по-възрастни, отколкото ние все още не можем да си спомним, че на 16-годишна възраст Дж. Бул преподава в селско училище и до 20-годишна възраст открива своето училище в Линкълн. Математикът напълно усвоил пет чужди езика, а в свободното си време бе прочетен от произведенията на Нютон и Лагранен. И всичко това е за син на обикновен работник!

През 1839 г. Буле пръв изпраща своите научни статии в Кеймбридж Математически вестник. Ученият е на 24 години. Работата на Boole беше толкова интересна за членовете на Кралското научно дружество, че през 1844 г. получи медал за приноса си за развитието математически анализ. Няколко други публикувани произведения, в които са описани елементи от математическата логика, позволяват на младия математик да заеме поста на професор в колеж Cork County College. Спомнете си, че той самият не е бил образован.

идея

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

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

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

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

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

• отчети;
• логически операции;
• функции и закони.

Изявленията са всички утвърждаващи изрази, които не могат да бъдат интерпретирани двойно. Те са написани под формата на числа (5> 3) или формулирани с обичайните думи (слонът е най-големият бозайник). В този случай фразата "жирафа няма врата" също има право да съществува, само булевата алгебра ще я определи като "лъжа".

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

Операции на булева алгебра

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

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

Основни логически действия

Най-често срещаните операции при булеви операции са отрицание (НЕ) и логически AND и OR. Така че можете да опишете почти всички действия в алгебра на преценките. Ще разгледаме подробно всяка една от трите операции.

Отричането (не) се отнася само за един елемент (операнд). Следователно операцията за отрицание се нарича unary. Използвайте следните символи, за да напишете не-A концепция: не-A, Amacr-macr-macr- или! A. В таблична форма тя изглежда така:

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

Логическо умножение и добавяне

Логическата АН се нарича операция за свързване. Какво означава това? Първо, че може да се приложи към два операнда, т.е. аз съм двоична операция. На второ място, само в случая с истината и на двата операнда (и А, и В) самият израз е вярно. Поговорката "Търпението и работата ще се съпротивляват" предполага, че само два фактора ще помогнат на човек да се справи с трудностите.

За писане се използват символите Aand-B, Asdot-B или AB.

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

Разграничаването се нарича логическа операция "ИЛИ". Приема стойност на истината, когато поне един от тях изявленията са верни (или А или В). Написано е така: Aor-B, A + B или A || B. Историческите таблици за тези операции са:

Раздялата е като аритметично допълнение. Действието на логическото добавяне има само едно ограничение: 1 + 1 = 1. Но ние помним, че в цифровия формат математическата логика е ограничена до 0 и 1 (където 1 е вярна, 0 е невярна). Например изявлението "в музея можете да видите шедьовър или срещнете интересен събеседник" означава, че можете да видите произведения на изкуството и да се запознаете с един интересен човек. В същото време не е изключена възможността за едновременно изпълнение на двете събития.

Функции и закони

Значи вече знаем какви логически операции използва булевата алгебра. Функциите описват всички свойства на елементите на математическата логика и ви позволяват да опростите сложните съставни условия на задачите. Най-разбираемият и прост е собствеността на изоставянето на производни операции. Дериватите са изключителни ИЛИ, импликация и равностойност. Тъй като ние само се запознахме с основните операции, ние ще разгледаме само техните свойства.

асоциативност означава, че в изрази като "и А, Б и Б", изброяването на операндите няма значение. Формулата е следната:

(Aand-B) и -В = Aand- (Band-B) = Aand-Band-B,

(Aor-B) или -В = Aor- (Bor-B) = Aor-Bor-B.

Както виждаме, това е характерно не само за съюзи, но и за разединения.

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

Aand-B = Band-A-Aor-B = BOR-A.

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

Aand- (Bor-B) = Aand-Bor-Aand-B-Aor-Band-В = (Aor-B) и- (Aor-B).

Свойства на устройството и нула, който може да бъде един от операндите, също са аналогични на алгебричното умножение с нула или едно и допълнение към едно:

Aand-0 = 0, Aand-1 = A-Aor-0 = A, Aor-1 = 1.

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

Бан-Б = Б- Бор-Б = Б.

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

Aand-Bor-B = B- (Aor-B) и В = В.

Последователност на операциите

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

1. Отказ.

2. Свързване.

3. Разделяне с изключение на OR.

4. Последици, еквивалентност.

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

Функции за импликация и еквивалентност

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

Последици или логически последствия е изявление, в което едно действие е условие, а другото е следствие от неговото изпълнение. С други думи, това изречение с претекст "ако ... тогава". - Харесваш да яздиш, да обичаш и да се шегуваш да носиш. Това означава, че за кънки е необходимо да се затегнат шейната до хълма. Ако няма желание да напуснете планината, тогава не е нужно да носите шейни. Написано е така: A → B или ArArr-B.

Еквивалентността предполага, че резултантното действие възниква само когато и двата операнда са верни. Например, нощта се заменя от деня (и само тогава), когато слънцето изгрява от хоризонта. На езика на математическата логика, това изречение е написано като: Aequiv-B, AhArr-B, A == B.

Други закони на булевата алгебра

Разузнавателната алгебра се развива и много заинтересовани учени са формулирали нови закони. Най-известните са постулатите на шотландския математик О. де Морган. Той забеляза и определи такива свойства като близко отрицание, добавяне и двойно отрицание.

Затворете отрицанието предполага, че няма нито едно отрицание преди скобата: не (A или B) = не A или NOT B.

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

Band-не-B = 0-Bor-не-B = 1.

И накрая, двойно отрицание се компенсира. Т.е. Преди операнда или отрицанието изчезва, или остава само един.

Как да решим тестовете

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

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

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