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

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

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

1. Образователни:
   1. Научете се да съставяте логически изрази от изявления
   2. Въведете понятието „таблица на истината“
   3. Разгледайте последователността от действия за изграждане на таблици на истината
   4. Научете се да намирате смисъла на логическите изрази, като изграждате таблици на истината
   5. Въведете концепцията за еквивалентност на логическите изрази
   6. Научете се да доказвате еквивалентността на логическите изрази с помощта на таблици за истинност
   7. Укрепване на уменията за намиране на стойностите на логическите изрази чрез изграждане на таблици на истината
2. Развиващи се:
   1. Развивайте логическо мислене
   2. Развивайте вниманието
   3. Развивайте паметта
   4. Развивайте речта на учениците
3. Образователни:
   1. Развивайте способността да слушате учители и съученици
   2. Образувайте точността на водене на тефтер
   3. Насърчаване на дисциплината

По време на часовете

Организиране на времето

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

Проверка на домашната работа

Напишете на дъската решението на битовите проблеми
Всички други отварят тетрадки, ще прегледам, ще проверя как сте си свършили домашното
Нека повторим логическите операции още веднъж
В какъв случай сложното твърдение ще бъде вярно в резултат на операцията на логическо умножение?
Съставено изявление, образувано в резултат на операцията на логическо умножение, е вярно, ако и само ако всички прости твърдения, включени в него, са верни.
Кога сложното изявление ще бъде невярно в резултат на логическа операция за добавяне?
Съставено изявление, образувано в резултат на логическа операция на добавяне, е невярно, когато всички прости изявления, включени в него, са неверни.
Как инверсията влияе върху изявление?
Инверсията прави вярно твърдение невярно и обратно, невярно - вярно.
Какво можете да кажете за импликацията?
Логическото следване (импликация) се формира чрез комбиниране на две твърдения в едно с помощта на обрата на речта „ако ... тогава ...“.
Означава се А-> V
Съставено изявление, образувано от операцията на логическо следване (импликация), е невярно, ако и само ако грешен извод следва от истинската предпоставка (първото твърдение) (второто твърдение).
Какво можете да кажете за логическата операция на еквивалентност?
Логическото равенство (еквивалентност) се формира чрез комбиниране на две твърдения в едно с помощта на обрат на речта "... ако и само ако ...", "... ако и само ако ..."
Съставено изявление, образувано от логическа операция на еквивалентност, е вярно, ако и само ако и двете твърдения са или неверни, или верни едновременно.

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

Добре, повторихме материала, който разгледахме, и сега преминаваме към нова тема.

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

Нека да разгледаме отново нашия пример от последния урок.

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

При изграждането на таблици на истината има определена последователност от действия. Нека запишем

1. Необходимо е да се определи броят на редовете в таблицата на истината.

• брой редове = 2 n, където n е броят на логическите променливи

Те го записаха. Изграждане на таблица на истината
Какво правим първо?
Определете броя на колоните в таблица
Как го правим?
Преброяваме броя на променливите. В нашия случай логическата функция съдържа 2 променливи
Който?
А и Б
Колко реда ще има в таблицата?
Броят редове в таблицата на истината трябва да бъде 4.
Ами ако има 3 променливи?
Брой редове = 2³ = 8
Точно така. Какво да правим по -нататък?
Определете броя на колоните = броя на булевите променливи плюс броя на булевите операции.
Колко ще бъде в нашия случай?
В нашия случай броят на променливите е две, а броят на логическите операции е пет, тоест броят на колоните в таблицата с истината е седем.
Добре. По -далеч?
Изграждаме таблица с посочения брой редове и колони, обозначаваме колоните и въвеждаме в таблицата възможни набори от стойности на първоначалните логически променливи и попълваме таблицата на истината по колони.
Коя операция ще извършим първо? Просто помислете за скоби и приоритети
Можете първо да направите логическо отрицание или да намерите стойността първо в първата скоба, след това обратното и стойността във втората скоба, след това стойността между тези скоби

Сега можем да определим стойността на булева функция за всеки набор от булеви променливи
Сега записваме елемента "Еквивалентни логически изрази".
Булевите изрази, в които последните колони от таблиците на истината съвпадат, се извикват еквивалентен.Знакът „=“ се използва за обозначаване на еквивалентни логически изрази,
Нека докажем, че логическите изрази ┐ А & ┐В и AvB са еквивалентни. Нека първо изградим таблицата на истината на логическия израз

Колко колони ще има в таблицата? 5
Коя операция ще извършим първо? Инверсия A, инверсия B

Сега нека изградим таблицата на истината на логическия израз AvB
Колко реда ще има в таблицата? 4
Колко колони ще има в таблицата? 4

Всички разбираме, че ако трябва да намерим отрицанието за целия израз, тогава приоритетът в нашия случай принадлежи на дизъюнкцията. Затова първо извършваме дизъюнкцията и след това инверсията. Освен това можем да пренапишем нашия логически израз AvB. Защото трябва да намерим отрицанието на целия израз, а не на отделни променливи, тогава обратното може да бъде взето извън скобите ┐ (AvB) и знаем, че първо намираме стойността в скоби

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

Разрешаване на проблеми

1.

Колко променливи съдържа тази формула? 3
Колко реда и колони ще има в таблицата? 8 и 8
Каква ще бъде последователността на операциите в нашия пример? (инверсия, операции в скоби, операция в скоби)

2. Докажете с помощта на таблиците на истината еквивалентността на следните логически изрази:

(A → B) И (Av┐B)

Какъв извод правим? Тези булеви изрази не са еквивалентни

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

Докажете с помощта на таблици на истината, че логически изрази

VA v ┐B и A & B са еквивалентни

Обяснение на новия материал (продължение)

Използваме понятието „таблица на истината“ няколко поредни урока и какво е таблицата на истината, как смятате?
Таблица на истината е таблица, която установява съответствие между възможните набори от стойности на логически променливи и стойностите на функциите.
Как свършихте домашното, какъв беше вашият извод?
Изразите са еквивалентни
Не забравяйте, че в предишния урок направихме формула от сложно изявление, замествайки прости твърдения 2 * 2 = 4 и 2 * 2 = 5 с променливи A и B
Сега нека се научим да правим логически изрази от изявления.

Запишете заданието

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

1) Ако Иванов е здрав и богат, значи е здрав

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

А - Иванов е здрав
Б - Иванов е богат

Добре, тогава как ще изглежда формулата тогава? Само не забравяйте, за да не се загуби смисълът на изявлението, поставете скоби във формулата

2) Число е просто, ако е делимо само на 1 и само по себе си

A - числото се дели само на 1
B - числото се дели само на себе си
C - числото е просто

3) Ако числото се дели на 4, то се дели на 2

А - делимо на 4
B - делимо на 2

4) Произволно число е или делимо на 2, или делимо на 3

А - делимо на 2
B - делимо на 3

5) Един спортист подлежи на дисквалификация, ако се държи неправилно по отношение на съперник или съдия и ако е взел „допинг“.

А - спортистът подлежи на дисквалификация
B - държи се неправилно спрямо противника
С - държи се некоректно спрямо съдията
D - взе "допинг".

Разрешаване на проблеми

1. Изградете таблица на истината за формула

((p & q) → (p → r)) v p

Обяснявайки колко редове и колони ще има в таблицата? (8 & 7) Каква ще бъде последователността на операциите и защо?

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

Формулата се нарича закон на логиката или тавтология, ако приема същата стойност „true“ за всеки набор от стойности на променливите, включени в тази формула.
И ако всички стойности са невярни, какво мислите за такава формула?
Можем да кажем, че формулата не е осъществима

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

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

1. Ако капитанът на кораба получи специална инструкция, той трябва да напусне пристанището на своя кораб.
2. Ако капитанът не получи специални инструкции, тогава той не трябва да напуска пристанището, или отсега нататък ще бъде лишен от допускане до това пристанище.
3. Капитанът или е отказан достъп до това пристанище, или не получава специални инструкции

Ние идентифицираме прости изявления, съставяме формули

• А - капитанът получава специална инструкция
• B - напуска пристанището
• С - е лишен от достъп до пристанището

1. ┐А → (┐В v С)
2. С v ┐А

3. Запишете съставното изявление „(2 * 2 = 4 и 3 * 3 = 9) или (2 * 2 ≠ 4 и 3 * 3 ≠ 9)“ под формата на логически израз. Изградете таблица на истината.

A = (2 * 2 = 4) B = (3 * 3 = 9)

(A & B) v (┐A & ┐B)

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

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

1. A&V или ЦРУ;
2. (А или В) и (А или В);
3. А и (В или В);
4. A или (не B или не C).

Изберете линиите, където
и изписваме съюзите на всички променливи, освен това, ако променлива в този набор е равна на 1, тогава я записваме, а ако променливата = 0, тогава нейното отрицание.

За този пример

съединението на тези разединения ще бъде желаната формула:

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

Числото 1 се счита за елементарна връзка на ранг 0. Променлива се счита за елементарна връзка или елементарна дизъюнкция от ранг 1. Числото 0 се счита за елементарна дизъюнкция от ранг 0. Всяка връзка на променливи, която не е идентично невярна, може да бъде редуциран до елементарна форма и всяко разединение на букви, което не е идентично вярно, също може да бъде редуцирано до елементарна форма. За това е необходимо да се приложат свойствата на комутативност, идемпотентност и асоциативност на конюнкцията и дизюнкцията.

Строго е доказано, че всяка формула на булева алгебра може да бъде изразена с помощта на операциите , &, . Интуитивно този факт е очевиден, нека си припомним алгоритъма за съставяне на формула според таблицата на истината. Ние обаче използваме само тези операции. Тази форма на запис се нарича дизъюнктивна нормална форма(DNF). Това е един вид механизъм за нормализиране на формулите на логическата алгебра.

Определение: DNFЕ дизъюнкция на различни елементарни съюзи (т.е. всяка връзка се състои от елементарни твърдения или техните отрицания).

CNF се дефинира по подобен начин - конюнктивна нормална форма.

Определение: Ако в DNF всички елементарни съюзи имат същия ранг, равен на броя на променливите, от които зависи DNF, тогава той се нарича перфектен (SDNF).

Теорема. За всяка функция, която не е идентично невярна, има уникален SDNF.

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

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

Системи (&, , ); (, ); (&, ), (/) - са функционално завършени

(&, ) - функционално непълна.

Ние ще приемем тези факти без доказателства и когато решаваме проблеми, ще се опитаме да представим всяка формула, използвайки (&, , ). По -късно ще обсъдим по -подробно въпроса за функционалната пълнота и непълнотата на системата от операции.

Тема 1.7. Методи за опростяване на логически изрази. Методи за решаване на логически задачи.

Нека разгледаме пример за решаване на логически проблем.

Пример :

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

Ако Арбузов отиде, тогава Брюквин или Вишневски трябва да отидат

Ако Арбузов и Вишневски отидат, тогава Брюквин ще отиде

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

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

- Арбузов ще отиде

- Брюквин ще отиде

- Вишневски ще отиде

Тогава разработените условия за формирането на експедицията ще изглеждат така:

Нека съставим обща формула и опростим израза

тези. ако Арбузов отиде, тогава ще отиде Брюквин.

Пример:

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

- добро време

- ще отидем на плаж

- ще отидем в гората

Сега нека конструираме отрицанието на тази фраза.

тогава. получаваме поговорката „Утре времето ще е хубаво и няма да ходим в гората и на плажа.

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

Пример :

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

Ето какво казаха те:

Браун: Направих го. Джон не е виновен. (B & D)

Джон: Браун не е виновен. Престъпникът Смит. (B & C)

Смит: Аз не съм виновен. Blame Brown (C & B)

Нека да опишем официално тези твърдения:

- престъплението е извършено от Браун

- престъплението е извършено от Йоан

- престъплението е извършено от Смит

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

Кафяво:

Джон:

Смит:

Защото според условията на проблема, две от тези & са неверни и едното е вярно, тогава

Нека съставим таблица на истината

Остава само случай 2, т.е. престъпникът Смит и двете му твърдения са фалшиви.

следователно - невярно и - вярно

= 1 - Джон скъпи старец

Остава, че Браун е длъжностно лице и оттогава - фалшиво, значи - истина е.

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

Пример :

Упражнението:

Алгебра на логиката

Алгебра на логиката

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

Основателят на алгебрата на логиката е английският математик и логик Дж. Бул (1815-1864), който основава своето логическо учение на аналогията между алгебрата и логиката. Той е записал всяко твърдение, използвайки символите на езика, който е разработил, и е получил „уравнения“, чиято истинност или неверност могат да бъдат доказани въз основа на определени логически закони, като законите на комутативността, разпределението, асоциативността и т.н.

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

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

Например „3 по 3 е равно на 9“, „Архангелск на север от Вологда“ са верни твърдения, а „Пет е по -малко от три“, „Марс е звезда“ са неверни.

Очевидно не всяко изречение може да бъде логично твърдение, тъй като не винаги има смисъл да се говори за неговата невярност или истина. Например твърдението „Информатиката е интересен предмет“ е неясно и изисква допълнителна информация, а твърдението „За ученик от 10-ти клас А. А. Иванов информатиката е интересен предмет“, в зависимост от интересите на А. А. Иванов, може да отнеме относно значението на „истина“ или „лъжа“.

с изключение двузначна алгебра с предложения, в който се приемат само две стойности - „вярно“ и „невярно“, има многозначна алгебра на предложения.В такава алгебра в допълнение към стойностите „true“ и „false“ се използват такива стойности на истината като „вероятно“, „възможно“, „невъзможно“ и т.н.

В алгебрата логиките се различават прост(елементарно) изказвания, обозначени с латински букви (A, B, C, D, ...), и комплекс(композитен), съставен от няколко прости, използващи логически съединители, например, като например „Не“, „и“, „или“, „тогава и само тогава“, „ако ... тогава“... Истината или невярността на сложните твърдения, получени по този начин, се определя от значението на простите твърдения.

Нека обозначим като Аизявлението "Алгебрата на логиката се прилага успешно в теорията на електрическите вериги", и чрез V- "Алгебрата на логиката се използва при синтеза на релейно-контактни вериги."

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

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

Има само две логически стойности: вярно вярно)и невярно (FALSE)... Това съответства на цифровото представяне - 1 и 0 ... Резултатите от всяка логическа операция могат да бъдат записани под формата на таблица. Такива таблици се наричат ​​таблици на истината.

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

1. Логическо отрицание, инверсия(лат. инверсия- инверсия) - логическа операция, в резултат на която от дадено изявление се получава ново изявление (например A) ( не А), който се нарича отрицание на оригиналното изявление, обозначени символично с лента по-горе ($ A↖ (-) $) или с такива конвенции като ¬, "не", и гласи: "Не A", "A е невярно", "не е вярно, че A", "отрицание на A"... Например „Марс е планета на Слънчевата система“ (казвайки А); „Марс не е планета на Слънчевата система“ ($ A↖ (-) $); твърдението „10 е просто число“ (изявление В) е невярно; твърдението „10 не е просто число“ (изявление В) е вярно.

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

Изразът $ A↖ (-) $ е невярно, когато A е вярно и вярно, когато A е невярно.

Геометрично отрицанието може да бъде представено по следния начин: ако A е някакъв набор от точки, тогава $ A↖ (-) $ е допълването на множеството A, тоест всички точки, които не принадлежат към множеството A.

2.Съчетание(лат. конюнктио- връзка) - логическо умножение, операция, която изисква най -малко две логически стойности (операнди) и свързва две или повече инструкции, използвайки връзка "и"(например, "А и В"), който символично се обозначава със знака ∧ (A ∧ B) и гласи: „A и B“. Следните знаци се използват и за обозначаване на връзка: A ∙ B; A & B, A и B, а понякога между изказванията не се поставя знак: AB. Пример за логическо умножение: "Този триъгълник е равнобедрен и прав ъгъл." Дадено твърдение може да бъде вярно само ако са изпълнени и двете условия, в противен случай изявлението е невярно.

Неустойчивост А ∧ Vе вярно само ако и двете твърдения - Аи Vса верни.

Геометрично съединението може да бъде представено по следния начин: ако А, Б А ∧ Vима пресичане на множества Аи V.

3. Разединение(лат. разединение- разделяне) - логическо допълнение, операция, която свързва две или повече инструкции, използвайки пакет "или"(например, "А или В"), което символично се обозначава със знака ∨ (А∨ V)и чете: "А или В"... Следните знаци се използват и за обозначаване на разединение: A + B; А или В; А | Б... Пример за логическо добавяне: "Числото x се дели на 3 или 5". Това твърдение ще бъде вярно, ако са изпълнени и двете условия или поне едно от условията.

Таблицата на истината на операцията има формата

Неустойчивост А∨ Vневярно само ако и двете твърдения - Аи Vса фалшиви.

Геометрично логическото допълнение може да бъде представено по следния начин: ако А, БИма ли тогава някои набори от точки А ∨ VТова е обединението на множествата Аи V, тоест фигурата, обединяваща както квадрата, така и окръжността.

4. Строго разделяне на дизъюнкцията, добавяне по модул две- логическа операция, която свързва две изявления с помощта на връзка "или", използвани в изключителен смисъл, който символично се обозначава със знаците ∨ ∨ или ⊕ ( А ∨ ∨ Б, А ⊕ V) и чете: „Или А или В“... Пример за добавяне по модул две е поговорката „Този ​​триъгълник е тъп или остроъгълен“. Твърдението е вярно, ако някое от условията е изпълнено.

Таблицата на истината на операцията има формата

Твърдението A ⊕ B е вярно само когато твърденията A и B имат различни значения.

5. Извод(лат. implisito- тясно свързана) - логическа операция, която свързва два израза с помощта на пакет "Ако ... тогава"в сложно изявление, което символично се обозначава със знака → (( А → V) и чете: "Ако A, тогава B", "A води до B", "B следва от A", "A предполага B"... Знакът ⊃ (A ⊃ B) също се използва за обозначаване на импликацията. Пример за импликация: "Ако полученият четириъгълник е квадрат, тогава кръг може да бъде описан около него." Тази операция свързва два прости логически израза, първият е условие, а вторият е следствие. Резултатът от операция е невярен само когато предпоставката е вярна и ефектът е невярен. Например, „Ако 3 * 3 = 9 (A), тогава Слънцето е планета (B)“, резултатът от импликацията A → B е невярен.

Таблицата на истината на операцията има формата

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

6. Еквивалентност, двойна импликация, еквивалентност(лат. aequalis- равно и валентинка- валиден) - логическа операция, която позволява две изявления Аи Vвземете ново изявление A ≡ Bкойто гласи: "A е еквивалентно на B"... Следните символи също се използват за означаване на еквивалентност: ⇔, ∼. Тази операция може да бъде изразена чрез връзки „Тогава и само тогава“, „необходимо и достатъчно“, „еквивалент“... Пример за еквивалентност е изявлението: "Триъгълникът ще бъде правоъгълен тогава и само ако един от ъглите е 90 градуса."

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

Операцията на еквивалентност е противоположна на добавянето по модул две и има резултат „true“, ако и само ако стойностите на променливите съвпадат.

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

Приоритетът при извършване на логически операции е както следва: отрицание ( "не") има най -висок приоритет, след това съвместно ( "и"), след свързване - дизъюнкция ( "или").

С помощта на логически променливи и логически операции всяко логическо изявление може да бъде формализирано, тоест заменено с логическа формула. В същото време елементарните твърдения, които образуват сложно изявление, могат да бъдат напълно несвързани по значение, но това не пречи на определянето на истинността или неточността на сложното твърдение. Например изявлението „Ако пет е повече от две ( А), тогава вторник винаги идва след понеделник ( V) "- намек А→ V, а резултатът от операцията в този случай е „истина“. В логическите операции значението на изявленията не се взема предвид, а се взема предвид само тяхната истина или невярност.

Помислете например за изграждането на сложно изявление от изрази Аи Vкоето би било невярно тогава и само ако и двете твърдения са верни. В таблицата на истината за операцията на събиране по модул две откриваме: 1 ⊕ 1 = 0. И твърдението може да бъде например това: "Тази топка е напълно червена или напълно синя." Следователно, ако изявлението А„Тази топка е напълно червена“ е вярно и твърдението V„Тази топка е напълно синя“ е вярно, тогава сложното твърдение е лъжа, защото топката не може да бъде едновременно червена и синя.

Примери за решаване на проблеми

Пример 1.Определете за посочените стойности на X стойността на логическия израз ((X> 3) ∨ (X< 3)) → (X < 4) :

1) X = 1; 2) X = 12; 3) X = 3.

Решение.Последователността на операциите е следната: първо се извършват сравнителните операции в скоби, след това разединяването и последната е операцията за импликация. Операцията за разединяване ∨ е невярна тогава и само ако и двата операнда са неверни. Таблицата на истината за импликацията е

От тук получаваме:

1) за X = 1:

((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;

2) за X = 12:

((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;

3) за X = 3:

((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.

Пример 2.Посочете набора от цели числа X, за които израза ¬ ((X> 2) → (X> 5)) е вярно.

Решение.Операцията на отрицание се прилага към целия израз ((X> 2) → (X> 5)), следователно, когато изразът ¬ ((X> 2) → (X> 5)) е верен, изразът ((X > 2) → (X> 5)) е невярно. Следователно е необходимо да се определи за кои стойности на X изразът ((X> 2) → (X> 5)) е невярен. Импликационната операция приема стойността „false“ само в един случай: когато от истината следва false. И това се прави само за X = 3; X = 4; X = 5.

Пример 3.За коя от дадените думи изявлението ¬ (първа буква на гласна ∧ трета буква на гласна) ⇔ е низ от 4 знака? 1) assa; 2) куку; 3) царевица; 4) грешка; 5) силен мъж.

Решение.Нека разгледаме последователно всички предложени думи:

1) за думата дупе получаваме: ¬ (1 ∧ 0) ⇔ 1, 1 ⇔ 1 - твърдението е вярно;

2) за думата куку получаваме: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 - твърдението е вярно;

3) за думата царевица получаваме: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 - твърдението е невярно;

4) за думата грешка получаваме: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 - твърдението е вярно;

5) за думата силен човек получаваме: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 - твърдението е невярно.

Булевите изрази и тяхното преобразуване

Под логически изразтрябва да разберете такъв запис, който може да приеме логическата стойност „true“ или „false“. С това определение е необходимо да се разграничат логическите изрази:

• изрази, които използват сравнителни операции ("по -голямо от", "по -малко от", "равно", "не равно" и т.н.) и приемат логически стойности (например изразът a> b, където a = 5 и b = 7, е равно на стойността "false");
• директни логически изрази, свързани с логически стойности и логически операции (например A ∨ B ∧ C, където A = вярно, B = невярно и C = вярно).

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

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

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

Пример.Намерете стойността на израз:

$ 1 ≤ a ∨ A ∨ sin (π / a - π / b)< 1 ∧ ¬B ∧ ¬(b^a + a^b >a + b ∨ A ∧ B) $ за a = 2, b = 3, A = вярно, B = невярно.

Решение.Редът на отчитане на стойностите:

1) b a + a b> a + b, след заместване получаваме: 3 2 + 2 3> 2 + 3, т.е. 17> 2 + 3 = вярно;

2) A ∧ B = вярно ∧ невярно = невярно.

Следователно изразът в скоби е (b a + a b> a + b ∨ A ∧ B) = true ∨ false = true;

3) 1≤ a = 1 ≤ 2 = вярно;

4) sin (π / a - π / b)< 1 = sin(π/2 - π/3) < 1 = истина.

След тези изчисления най -накрая получаваме: истина ∨ A ∧ вярна ∧ ¬В ∧ ¬истина.

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

5) ¬В = ¬фал = вярно; ¬истина = невярно;

6) A ∧ вярно ∧ вярно ∧ невярно = вярно ∧ вярно ∧ вярно ∧ невярно = невярно;

7) вярно ∨ невярно = вярно.

По този начин резултатът от булево изражение на дадените стойности е „истина“.

Забележка.Като се има предвид, че първоначалният израз е в крайна сметка сумата от два члена, а стойността на един от тях е 1 ≤ a = 1 ≤ 2 = вярно, без допълнителни изчисления можем да кажем, че резултатът за целия израз също е "вярно".

Идентични преобразувания на логически изрази

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

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

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

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

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

1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 = X1 ∧ X2 ∨ ¬X1 ∧ X2 = (X1 ∨ ¬X1) ∧ X2 = 1 ∧ X2 = X2.

За трансформация тук можете да приложите закона за идемпотентност, закона за разпределение; обратна променлива операция и постоянна операция.

2) X1 ∨ X1 ∧ X2 = X1 ∨ (1 ∨ 1 ∧ X2) = X1 ∨ (1 ∨ X2) = X1.

Тук за простота се прилага законът на поглъщане.

3) ¬ (X1 ∧ X2) ∨ X2 = (¬X1 ∨ ¬X2) ∨ X2 = ¬X1 ¬ ¬X2 ∨ X2 = ¬X1 ∨ 1 = 1.

При трансформиране, правилото на де Морган, се прилага операцията на променлива с нейната инверсия, операция с константа

Примери за решаване на проблеми

Пример 1.Намерете булев израз, еквивалентен на A ∧ ¬ (¬B ∨ C).

Решение.Прилагаме правилото на де Морган за В и С: ¬ (¬B ∨ C) = B ∧ ¬C.

Получаваме израз, еквивалентен на оригиналния: A ∧ ¬ (¬B ∨ C) = A ∧ B ∧ ¬C.

Отговор: A ∧ B ∧ ¬C.

Пример 2.Посочете стойността на логическите променливи A, B, C, за които стойността на логическия израз (A ∨ B) → (B ∨ ¬C ∨ B) е невярна.

Решение.Операцията на импликация е невярна само в случай, когато фалшивост следва от истинската предпоставка. Следователно, за даден израз, предпоставката A ∨ B трябва да приеме стойността „true“, а последствието, тоест изразът B ∨ ¬C ∨ B, трябва да бъде „false“.

1) A ∨ B - резултатът от разединението е „вярно“, ако поне един от операндите е „истина“;

2) B ∨ ¬C ∨ B - изразът е невярен, ако всички термини имат стойността „false“, тоест B - „false“; ¬C - "false" и следователно променливата C има стойността "true";

3) ако разгледаме предпоставката и вземем предвид, че B е „невярно“, тогава получаваме, че стойността на A е „вярно“.

Отговор: A е вярно, B е невярно, C е истина.

Пример 3.Кое е най -голямото цяло число X, за което изразът (35

Решение.Нека запишем таблицата на истината за импликационната операция:

Израз X< (X - 3) ложно при любых положительных значениях X. Следовательно, для того чтобы результатом импликации была «истина», необходимо и достаточно, чтобы выражение 35 < X · X также было ложно. Максимальное целое значение X, для которого 35 < X · X ложно, равно 5.

Отговор: X = 5.

Използване на булеви изрази за описание на геометрични региони

Булевите изрази могат да се използват за описание на геометрични области. В този случай проблемът е формулиран по следния начин: за даден геометричен регион запишете логически израз, който приема стойността „true“ за стойностите x, y тогава и само ако има точка с координати (x; y) принадлежи към геометричния регион.

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

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

1) .

Решение.Дадена геометрична област може да бъде представена като набор от следните области: първата област - D1 - полуравна $ (x) / ( - 1) + (y) / (1) ≤ 1 $, втората - D2 - окръжност с център в началото $ x ^ 2 + y ^ 2 ≤ 1 $. Тяхното пресичане D1 $ ∩ $ D2 е желаната област.

Резултат:булев израз $ (x) / (- 1) + (y) / (1) ≤ 1 ∧ x ^ 2 + y ^ 2 ≤ 1 $.

2)

Тази област може да бъде написана така: | x | ≤ 1 ∧ y ≤ 0 ∧ y ≥ -1.

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

Можете да решите обратната задача, а именно: нарисувайте област за даден логически израз.

Пример 2.Начертайте и засенчете област, за чиито точки логичното условие е изпълнено y ≥ x ∧ y + x ≥ 0 ∧ y< 2 .

Решение.Търсената площ е пресичането на три полуравнини. Ние градим върху равнината (x, y) прави линии y = x; y = -x; y = 2. Това са границите на областта, а последната граница y = 2 не принадлежи на областта, затова я чертаем с пунктирана линия. За да се удовлетвори неравенството y ≥ x, е необходимо точките да са отляво на линията y = x, а неравенството y = -x да важи за точките, които са вдясно от правата y = -x. Условие y< 2 выполняется для точек, лежащих ниже прямой y = 2. В результате получим область, которая изображена на рис.:

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

Логическите функции са много полезни за описване на работата на електрическите вериги. Така че, за схемата, показана на фиг., Където стойността на променливата X е състоянието на превключвателя (ако е включена, стойността на X е "true", а ако е изключена, е "false") , тази стойност на Y е състоянието на крушката (ако е включена - стойността е „true“, а ако не - „false“), логическата функция ще бъде записана по следния начин: Y = X. Извиква се функцията Y функция на проводимостта.

За схемата, показана на фиг., Логическата функция Y има формата: Y = X1 ∪ X2, тъй като един включен ключ е достатъчен, за да гори светлината. На диаграмата на фиг., За да гори светлината, двата превключвателя трябва да бъдат включени, следователно функцията за проводимост има формата: Y = X1 ∧ X2.

За по -сложна верига функцията на проводимост ще бъде: Y = (X11 ∨ (X12 ∧ X13)) ∧ X2 ∧ (X31 ∨ X32).

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

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

Използване на апарата на логическата алгебра при проектирането на логически схеми

Алгебрата на логическата математика е много удобна за описване на функционирането на компютърния хардуер. Всяка информация, когато се обработва на компютър, се представя в двоична форма, тоест тя се кодира от някаква последователност от 0 и 1. Обработката на двоични сигнали, съответстваща на 0 и 1, се извършва в компютъра чрез логически елементи. Логически порти, които изпълняват основни логически операции И, ИЛИ, НЕ,са показани на фиг.

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

Технически, компютърният логически елемент е реализиран във формата електрическа верига, което е връзка на различни части: диоди, транзистори, резистори, кондензатори. Входът на логически елемент, който също се нарича порта, приема електрически сигнали с високи и ниски нива на напрежение, а на изхода се подава и един изходен сигнал, висок или нисък. Тези нива съответстват на едно от състоянията двоична система: десет; TRUE е FALSE. Всеки логически елемент има свой символ, който изразява неговата логическа функция, но не посочва какъв вид електронна схема е внедрена в него. Това улеснява писането и разбирането на сложни логически схеми. Работата на логическите схеми е описана с помощта на таблици за истинност. Конвенционална нотация на веригата OR, знакът "1" - от остарялото обозначение на дизъюнкцията като "> = 1" (стойността на дизъюнкцията е 1, ако сумата от двата операнда е по -голяма или равна на 1). Знакът "&" в диаграмата AND е съкращение от английската дума и.

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

Изграждане на таблици на истината за булево изражение

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

Удобна форма на обозначение за намиране на стойностите на функция е таблица, съдържаща освен стойностите на променливите и стойностите на функцията и стойностите на междинните изчисления. Помислете за пример за изграждане на таблица на истината за формулата $ (X1) ↖ (-) ∧ X2 ∨ (X1 ∨ X2) ↖ (-) ∨ X1 $.

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

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

1. Разделителна нормална форма (DNF)- сумата от продукти, образувани от променливи и техните отрицания за фалшиви стойности.

Алгоритъмът за конструиране на DNF е следният:

1. в таблицата за истинност на функцията се избират набори аргументи, за които логическите форми са равни на 1 ("true");
2. всички избрани логически множества се записват като логически продукти на аргументи, последователно ги свързват помежду си чрез операцията на логическа сума (дизъюнкция);
3. за аргументи, които са невярни, операцията на отрицание се прилага към конструирания запис.

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

Решение.Избираме наборите от стойности на аргументи, в които функцията е равна на 1. Това са първият и четвъртият ред на таблицата (редът на заглавката не се взема предвид при номерирането).

Записваме логическите произведения на аргументите на тези множества, комбинирайки ги с логическа сума: X1 ∧ X2 ∨ X1 ∧ X2.

Пишем отрицанието по отношение на аргументите на избраните множества, които имат невярна стойност (четвъртият ред на таблицата; вторият набор във формулата; първият и вторият елемент): X1 ∧ X2 ∨ $ (X1) ↖ ( -) $ ∧ $ (X2) ↖ (-) $.

Отговор: F (X1, X2) = X1 ∧ X2 ∨ $ (X1) ↖ (-) $ ∧ $ (X2) ↖ (-) $.

2. Съединителна нормална форма (CNF)- продуктът на сумите, образувани от променливите, и техните отрицания за истинските стойности.

Алгоритъмът за конструиране на CNF е както следва:

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

Примери за решаване на проблеми

Пример 1.Помислете за предишния пример, тоест конструирайте функция, която определя, че първото число е равно на второто, използвайки метода CNF. За дадена функция нейната таблица на истината има формата

Решение.Избираме набори стойности на аргументи, в които функцията е равна на 0. Това са вторият и третият ред (редът на заглавието не се взема предвид при номерирането).

Записваме логическите суми на аргументите на тези множества, комбинирайки ги с логически продукт: X1 ∨ X2 ∧ X1 ∨ X2.

Пишем отрицанието спрямо аргументите на избраните множества, които имат истинска стойност (вторият ред на таблицата, първият набор от формулата, вторият елемент; за третия ред това е вторият набор от формулата, първият елемент): X1 ∨ $ (X2) ↖ (-) $ ∧ $ (X1) ↖ (-) $ ∨ X2.

По този начин е получен запис на логическата функция в CNF.

Отговор: X1 ∨ $ (X2) ↖ (-) $ ∧ $ (X1) ↖ (-) $ ∨ X2.

Стойностите на функциите, получени по двата метода, са еквивалентни. За да докажем това твърдение, използваме логическите правила: F (X1, X2) = X1 ∨ $ (X2) ↖ (-) $ ∧ $ (X1) ↖ (-) $ ∨ X2 = X1 ∧ $ (X1) ↖ (-) $ ∨ X1 ∧ X2 ∨ $ (X2) ↖ (-) $ ∧ $ (X1) ↖ (-) $ ∨ $ (X2) ↖ (-) $ ∧ X2 = 0 ∨ X1 ∨ X2 ∨ $ (X2 ) ↖ (-) $ ∧ $ (X1) ↖ (-) $ ∨ 0 = X1 ∧ X2 ∨ $ (X1) ↖ (-) $ ∧ $ (X2) ↖ (-) $.

Пример 2... Изградете булева функция за дадена таблица на истината:

Търсената формула: X1 ∧ X2 ∨ $ (X1) ↖ (-) $ ∧ X2.

Може да се опрости: X1 ∧ X2 ∨ $ (X1) ↖ (-) $ ∧ X2 = X2 ∧ (X1 ∨ $ (X1) ↖ (-) $) = X2 ∧ 1 = X2.

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

Търсената формула: X1 ∧ X2 ∧ X ∨ $ (X1) ↖ (-) $ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $ (X3) ↖ (-) $ ∪ X1 ∧ $ (X2) ↖ (-) $ ∧ $ (X3) ↖ (-) $.

Формулата е доста тромава и трябва да бъде опростена:

X1 ∧ X2 ∧ X3 ∨ $ (X1) ↖ (-) $ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $ (X3) ↖ (-) $ ∨ X1 ∧ $ (X2) ↖ (-) $ ∧ $ (X3) ↖ (-) $ = X2 ∧ X3 ∧ (X1 ∨ $ (X1) ↖ (-) $) ∨ X1 ∧ $ (X3) ↖ (-) $ ∧ (X2 ∨ $ (X2) ↖ (-) $) = X2 ∧ X3 ∨ X1 ∧ $ (X3) ↖ (-) $.

Таблици на истината за решаване на логически проблеми

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

Примери за решаване на проблеми

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

Решение.Очевидно решението ще доведе до таблица, в която необходимата функция Y (X1, X2, X3) ще има стойността "true", ако всяка две променливи имат стойността "true".

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

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

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

1. математика, компютърни науки, физика;
2. информатика, физика, математика.

Пример 3.Трима приятели дойдоха в спортния лагер - Петър, Борис и Алексей. Всеки от тях обича два спорта. Известно е, че има шест такива спорта: футбол, хокей, ски, плуване, тенис, бадминтон. Известно е също, че:

1. Борис е най -възрастният;
2. който играе футбол е по -млад от този, който играе хокей;
3. играе футбол и хокей, а Петър живее в една и съща къща;
4. когато възникне кавга между скиор и тенисист, Борис ги примирява;
5. Питър не може да играе тенис или бадминтон.

Какви спортове харесва всяко от момчетата?

Решение.Нека съставим таблица и да отразим в нея условията на задачата, като попълним съответните клетки с числата 0 и 1, в зависимост от това дали съответното твърдение е невярно или вярно.

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

От условие 4 следва, че Борис не обича ски или тенис, но от условия 3 и 5, че Петър не знае как да играе футбол, хокей, тенис и бадминтон. Следователно любимите спортове на Питър са ски и плуване. Нека въведем това в таблицата и попълваме останалите клетки от колоните „Ски“ и „Плуване“ с нули.

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

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

И накрая, разбираме, че Борис обича хокея и бадминтона. Финалната маса ще изглежда така:

Отговор:Петър обича ски и плуване, Борис играе хокей и бадминтон, а Алексей играе футбол и тенис.

Логическа функцияе функция, при която променливите приемат само две стойности: логическа единица или логическа нула ... Истината или неверността на сложните преценки е функция на истинността или неверността на прости. Тази функция се нарича Булева функция за преценка f (a, b) .

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

Редът за извършване на логически операции в сложен логически израз:

1. инверсия;

2. съединение;

3. разединение;

4. импликация;

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

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

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

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

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

брой редове = 2 n + ред за заглавка,

н- броят на прости изявления.

брой колони = брой променливи + брой логически операции;

o определяне на броя на променливите (прости изрази);

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

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

Пример:Създайте таблица на истината за логически израз:

D = A & (B  C).

Решение: 

1. Определете броя на редовете:

на входа има три прости изявления: A, B, C така че n = 3 и брой редове = 2 3 +1 = 9.

2. Определете броя на колоните:

o прости изрази (променливи): A, B, C ;

o междинни резултати (логически операции):

o А - инверсия (обозначава се с E );

o B  C е дизъюнкционната операция (ние обозначаваме с F );

o, както и желаната крайна стойност на аритметичния израз:

o D = A & (B  C) ... тези. D = E & F е операция на свързване.

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

Създайте логическа функция за дадена таблица на истината.

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

1. Изберете в таблицата на истината онези редове, в които е стойността на функцията 1 .

2. Изпишете необходимата формула под формата на разединение на няколко логически елемента. Броят на тези елементи е равен на броя на избраните редове.

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

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

Решение.

1. В първия и третия ред на таблицата на истината стойността на функцията е 1 .

2. Тъй като има два реда, получаваме разединение два елемента: () V () .

3. Всеки логически елемент в тази дизъюнкция е записан във формата съюзи аргументи на функцията х и Y : (X & Y) V (X & Y) .

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

5. Z (X, Y) = (X & Y) V (X & Y) .

Пример 4.Определете участника в престъплението въз основа на две предпоставки:

1) "Ако Иванов не участва или Петров участва, значи участва Сидоров";

2) 2) "Ако Иванов не е участвал, значи Сидоров не е участвал."

Решение

Нека съставим изрази:

Аз- „Иванов участва в престъплението“;

P- „Петров участва в престъплението“;

С- „Сидоров участва в престъплението“.

Нека напишем колетите под формата на формули:

Нека проверим резултата, като използваме таблицата на истината:

Отговор:Иванов е участвал в престъплението.

Броят на входните променливи в даден израз е три (A, B, C)... Следователно, броят на входните набори Q = 2 3 = 8.

Колоните на таблицата на истината съответстват на стойностите на оригиналните изрази A, B, C, междинни резултати и ( Б V ° С), както и желаната крайна стойност на сложен аритметичен израз:

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

Логическа функция- функция, чиито променливи приемат една от двете стойности: $ 1 $ или $ 0 $.

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

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

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

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

Еквивалентенсе извикват логически изрази, чиито последни колони от таблиците на истината съвпадат. Еквивалентността е обозначена със знака $ "=" $.

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

Снимка 1.

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

Алгоритъм за конструиране на таблицата на истинността на логическа функция

Определете броя на редовете: брой редове= $ 2 ^ n + 1 $ (за заглавната лента), $ n $ - броят на прости изрази. Например, за функции на две променливи има $ 2 ^ 2 = 4 $ комбинации от набори от стойности на променливи, за функции на три променливи - $ 2 ^ 3 = 8 $ и т.н.

Определете броя на колоните: брой колони = брой променливи + брой логически операции.При определяне на броя на логическите операции се взема предвид и редът на тяхното изпълнение.

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

Фигура 2.

Пример 1

Създайте таблица на истината за логическия израз $ D = \ bar (A) \ vee (B \ vee C) $.

Решение:

Нека определим броя на редовете:

брой редове = $ 2 ^ 3 + 1 = 9 $.

Броят на променливите е $ 3 $.

1. инверсия ($ \ bar (A) $);
2. разединение, защото тя е в скоби ($ B \ vee C $);

3. disjunction ($ \ overline (A) \ vee \ left (B \ vee C \ right) $) е необходимият логически израз.

   Брой колони = $3 + 3=6$.

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

Фигура 3.

Пример 2

За този логически израз изградете таблица на истинността:

Решение:

Нека определим броя на редовете:

Броят на прости изрази е $ n = 3 $, така че

брой редове = $2^3 + 1=9$.

Нека определим броя на колоните:

Броят на променливите е $ 3 $.

Броят на логическите операции и тяхната последователност:

1. отрицание ($ \ bar (C) $);
2. разединение, защото тя е в скоби ($ A \ vee B $);
3. връзка ($ (A \ vee B) \ bigwedge \ overline (C) $);
4. отрицание, което обозначаваме $ F_1 $ ($ \ overline ((A \ vee B) \ bigwedge \ overline (C)) $);
5. дизюнкция ($ A \ vee C $);
6. връзка ($ (A \ vee C) \ bigwedge B $);
7. отрицание, което обозначаваме с $ F_2 $ ($ \ overline ((A \ vee C) \ bigwedge B) $);

8. дизъюнкцията е необходимата логическа функция ($ \ overline ((A \ vee B) \ bigwedge \ overline (C)) \ vee \ overline ((A \ vee C) \ bigwedge B) $).