Как се решават някои задачи в раздели А и Б на изпита по информатика

Урок #3. Логики. Логически функции. Решаване на уравнения

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

1. Комутативност на дизюнкция и конюнкция:
   a ˅ b ≡ b ˅ a
   a^b ≡ b^a
2. Разпределителен закон по отношение на дизюнкция и конюнкция:
   a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
   a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Отрицание на отрицанието:
   ¬(¬a) ≡ a
4. Консистенция:
   a ^ ¬а ≡ невярно
5. Изключително трето:
   a ˅ ¬а ≡ true
6. Законите на Де Морган:
   ¬(a ˅ b) ≡ ¬a ˄ ¬b
   ¬(a ˄ b) ≡ ¬a ˅ ¬b
7. Опростяване:
   a ˄ a ≡ a
   a ˅ a ≡ a
   a ˄ true ≡ a
   a ˄ false ≡ false
8. Абсорбция:
   a ˄ (a ˅ b) ≡ a
   a ˅ (a ˄ b) ≡ a
9. Замяна на импликацията
   a → b ≡ ¬a ˅ b
10. Подмяна на самоличността
    a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Представяне на логически функции

Всяка логическа функция от n променливи - F(x 1, x 2, ... x n) може да бъде определена от таблица на истинност. Такава таблица съдържа 2n набора от променливи, за всеки от които е посочена стойността на функция от този набор. Този метод е добър, когато броят на променливите е относително малък. Вече за n > 5 представянето става слабо видимо.

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

Системата от функции (¬, ˄, ˅) е пълна. Закони 9 и 10 са примери, демонстриращи как импликацията и идентичността се изразяват чрез отрицание, конюнкция и дизюнкция.

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

(a ˅ b) ≡ ¬(¬a ˄ ¬b)
(a ˄ b) ≡ ¬(¬a ˅ ¬b)

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

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

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

Проблем 15:

Даден е фрагмент от таблицата на истината. Коя от трите дадени функции отговаря на този фрагмент?

X 1	X 2	X 3	X 4	Е
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
3. ¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Функция номер 3.

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

Проблем 16:

Кое от дадените числа отговаря на условието:

(цифрите, като се започне от най-значимата цифра, са в низходящ ред) → (число - четно) ˄ (малка цифра - четно) ˄ (старша цифра - нечетно)

Ако има няколко такива числа, посочете най-голямото.

1. 13579
2. 97531
3. 24678
4. 15386

Условието е изпълнено от числото 4.

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

Задача 17: Двама свидетели дадоха следните показания:

Първи свидетел: Ако А е виновен, то Б е още по-виновен, а В е невинен.

Втори свидетел: Двама са виновни. А един от останалите определено е виновен и виновен, но не мога да кажа кой точно.

Какви изводи за вината на А, Б и В могат да се направят от свидетелските показания?

Отговор: От свидетелските показания следва, че А и Б са виновни, а В е невинен.

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

Първото нещо, което трябва да направите, е да формализирате изявленията. Нека въведем три логически променливи - A, B и C, всяка от които има стойност true (1), ако съответният заподозрян е виновен. Тогава показанията на първия свидетел се дават по формулата:

A → (B ˄ ¬C)

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

A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))

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

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

А	б	В	F 1	Е 2	F 1 ˄ F 2
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	0	0

Обобщените доказателства са верни само в един случай, което води до ясен отговор – А и Б са виновни, а В е невинен.

От анализа на тази таблица също следва, че показанията на втория свидетел са по-информативни. От истинността на неговото свидетелство следват само две неща: възможни варианти- А и Б са виновни, а В е невинен, или А и В са виновни, а Б е невинен. Показанията на първия свидетел са по-малко информативни - има 5 различни варианта, съответстващи на неговите показания. Заедно показанията на двамата свидетели дават ясен отговор за вината на заподозрените.

Логически уравнения и системи уравнения

Нека F(x 1, x 2, …x n) е логическа функция от n променливи. Логическото уравнение изглежда така:

F(x 1, x 2, …x n) = C,

Константата C има стойност 1 или 0.

Едно логическо уравнение може да има от 0 до 2 n различни решения. Ако C е равно на 1, тогава решенията са всички онези набори от променливи от таблицата на истината, за които функцията F приема стойност true (1). Останалите комплекти са решения на уравнението за C, равно на нула. Винаги можете да разглеждате само уравнения от вида:

F(x 1, x 2, …x n) = 1

Наистина, нека е дадено уравнението:

F(x 1, x 2, …x n) = 0

В този случай можем да отидем до еквивалентното уравнение:

¬F(x 1, x 2, …x n) = 1

Да разгледаме система от k логически уравнения:

F 1 (x 1, x 2, …x n) = 1

F 2 (x 1, x 2, …x n) = 1

F k (x 1, x 2, …x n) = 1

Решението на система е набор от променливи, за които всички уравнения на системата са удовлетворени. По отношение на логическите функции, за да се получи решение на система от логически уравнения, трябва да се намери набор, върху който логическата функция Ф е вярна, представляваща конюнкция на оригиналните функции F:

Ф = F 1 ˄ F 2 ˄ … F k

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

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

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

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

Проблем 18

Колко различни набора от стойности на логическите променливи x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 има, които удовлетворяват системата от две уравнения?

Отговор: Системата има 36 различни решения.

Решение: Системата от уравнения включва две уравнения. Нека намерим броя решения на първото уравнение в зависимост от 5 променливи - x 1, x 2, ...x 5. Първото уравнение от своя страна може да се разглежда като система от 5 уравнения. Както беше показано, системата от уравнения всъщност представлява конюнкция на логически функции. Обратното също е вярно: съвкупност от условия може да се разглежда като система от уравнения.

Нека изградим дърво на решенията за импликацията (x1→ x2) - първият член на конюнкцията, който може да се разглежда като първото уравнение. Ето как изглежда графичното представяне на това дърво:

Дървото се състои от две нива според броя на променливите в уравнението. Първото ниво описва първата променлива X 1 . Два клона на това ниво отразяват възможните стойности на тази променлива - 1 и 0. На второто ниво клоните на дървото отразяват само онези възможни стойности на променливата X 2, за които уравнението е вярно. Тъй като уравнението определя импликация, клон, на който X 1 има стойност 1, изисква на този клон X 2 да има стойност 1. Клон, на който X 1 има стойност 0, произвежда два клона със стойностите на X 2 равно на 0 и 1. Изграденото дърво дефинира три решения, върху които импликацията X 1 → X 2 приема стойност 1. На всеки клон се изписва съответен набор от променливи стойности, даващи решение на уравнението.

Тези набори са: ((1, 1), (0, 1), (0, 0))

Нека продължим да изграждаме дървото на решенията, като добавим следното уравнение, следното импликация X 2 → X 3 . Спецификата на нашата система от уравнения е, че всяко ново уравнение на системата използва една променлива от предишното уравнение, добавяйки една нова променлива. Тъй като променливата X 2 вече има стойности в дървото, тогава във всички клонове, където променливата X 2 има стойност 1, променливата X 3 също ще има стойност 1. За такива клонове конструкцията на дървото продължава към следващото ниво, но нови клонове не се появяват. Единичният клон, където променливата X 2 има стойност 0, ще се разклони на два клона, където променливата X 3 ще получи стойностите 0 и 1. По този начин всяко добавяне на ново уравнение, като се има предвид неговата специфика, добавя едно решение. Оригинално първо уравнение:

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
има 6 решения. Ето как изглежда пълното дърво на решенията за това уравнение:

Второто уравнение на нашата система е подобно на първото:

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

Единствената разлика е, че уравнението използва Y променливи. Това уравнение също има 6 решения. Тъй като всяко решение за променливите X i може да се комбинира с всяко решение за променливите Y j, общият брой решения е 36.

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

Проблем 19

Колко различни набора от стойности на логическите променливи x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 има, които отговарят на всички условия, изброени по-долу?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1
(x1→ y1) = 1

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

От уравнението X 1 → Y 1 следва, че когато X 1 има стойност 1 (съществува едно такова решение), тогава Y 1 също има стойност 1. По този начин има едно множество, на което X 1 и Y 1 имат стойностите ​​1. Когато X 1 е равно на 0, Y 1 може да има всякаква стойност, както 0, така и 1. Следователно, всеки набор с X 1, равен на 0, и има 5 такива набора, съответства на всичките 6 набора с Y променливи. Следователно общият брой на решенията е 31.

Проблем 20

(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1

Решение: Спомняйки си основните еквивалентности, ние записваме нашето уравнение като:

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1

Цикличната верига от импликации означава, че променливите са идентични, така че нашето уравнение е еквивалентно на уравнението:

X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1

Това уравнение има две решения, когато всички X i са 1 или 0.

Проблем 21

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1

Решение: Точно както в задача 20, преминаваме от циклични импликации към идентичности, пренаписвайки уравнението във формата:

(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1

Нека изградим дърво на решенията за това уравнение:

Проблем 22

Колко решения има следната система от уравнения?

((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X 4)) = 0

((X 3 ≡X 4) ˄ (X 5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X 5 ≡X 6)) = 0

((X 5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X 5 ≡X 6) ˄ ¬(X 7 ≡X 8)) = 0

((X 7 ≡X 8) ˄ (X 9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X 9 ≡X 10)) = 0

Отговор: 64

Решение: Нека преминем от 10 променливи към 5 променливи, като въведем следната промяна на променливите:

Y 1 = (X 1 ≡ X 2); Y 2 = (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 = (X 7 ≡ X 8); Y 5 = (X 9 ≡ X 10);

Тогава първото уравнение ще приеме формата:

(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0

Уравнението може да се опрости, като се запише като:

(Y 1 ≡ Y 2) = 0

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

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

Дървото на решенията за тази система е просто и се състои от два клона с редуващи се променливи стойности:

Връщайки се към оригиналните променливи X, имайте предвид, че за всяка стойност в променливата Y има 2 стойности в променливите X, така че всяко решение в променливите Y генерира 2 5 решения в променливите X. Двата клона генерират 2 * 2 5 решения, така че общият брой решения е 64.

Както можете да видите, всеки проблем за решаване на система от уравнения изисква свой собствен подход. Често срещана техника е извършването на еквивалентни трансформации за опростяване на уравненията. Често срещана техника е да се конструират дървета на решенията. Използваният подход отчасти напомня за конструирането на таблица на истината с тази особеност, че не се конструират всички набори от възможни стойности на променливи, а само тези, на които функцията приема стойност 1 (true). Често при предложените проблеми не е необходимо да се изгражда цялостно дърво на решенията, тъй като вече начален етапвъзможно е да се установи модел на появата на нови клонове на всяко следващо ниво, както беше направено например в задача 18.

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

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

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

Колкото и да е странно, задачата за намиране на решения на системи от логически уравнения е трудна за компютър и се оказва, че компютърът има своите граници. Компютърът може доста лесно да се справи със задачи, при които броят на променливите е 20-30, но ще започне да мисли за проблеми дълго време по-голям размер. Факт е, че функцията 2 n, която определя броя на комплектите, е експоненциална, която расте бързо с увеличаване на n. Толкова бързо, че обикновен персонален компютър не може да се справи със задача, която има 40 променливи на ден.

Програма на език C# за решаване на логически уравнения

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

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

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

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

Ето как изглежда функция в C#, която решава нашия проблем:

///

/// програма за отчитане на броя на решенията

/// логическо уравнение (система от уравнения)

///

///

/// логическа функция - метод,

/// чийто подпис е посочен от делегата на DF

///

/// брой променливи

/// брой решения

static int SolveEquations(DF fun, int n)

bool set = нов bool[n];

int m = (int)Math.Pow(2, n); //брой комплекти

int p = 0, q = 0, k = 0;

//Пълно търсене по брой набори

за (int i = 0; i< m; i++)

//Формиране на следващия набор - набор,

//определено от двоичното представяне на числото i

за (int j = 0; j< n; j++)

k = (int)Math.Pow(2, j);

//Изчисляване на стойността на функцията върху множеството

За разбиране на програмата се надявам обясненията на идеята на програмата и коментарите в нейния текст да са достатъчни. Ще се съсредоточа само върху обяснението на заглавието на дадената функция. Функцията SolveEquations има два входни параметъра. Забавният параметър указва логическа функция, съответстваща на решаваното уравнение или система от уравнения. Параметърът n указва броя на забавните променливи. В резултат на това функцията SolveEquations връща броя на решенията на логическата функция, т.е. броя на тези набори, за които функцията оценява като true.

Обичайно за учениците е, когато някои функции F(x) входен параметър x е променлива от аритметичен, низов или булев тип. В нашия случай се използва по-мощен дизайн. Функцията SolveEquations се отнася до функции от по-висок ред - функции от тип F(f), чиито параметри могат да бъдат не само прости променливи, но и функции.

Класът от функции, които могат да бъдат предадени като параметър на функцията SolveEquations, е посочен, както следва:

делегат bool DF(bool vars);

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

И накрая, ето една програма, която използва функцията SolveEquations за решаване на няколко системи от логически уравнения. Функцията SolveEquations е част от класа ProgramCommon по-долу:

клас ProgramCommon

делегат bool DF(bool vars);

static void Main(string args)

Console.WriteLine("И функции - " +

Решете уравнения(FunAnd, 2));

Console.WriteLine("Функцията има 51 решения - " +

Решаване на уравнения (Fun51, 5));

Console.WriteLine("Функцията има 53 решения - " +

Решаване на уравнения (Fun53, 10));

статичен bool FunAnd(bool vars)

return vars && vars;

статичен bool Fun51(bool vars)

f = f && (! vars || vars);

f = f && (! vars || vars);

f = f && (! vars || vars);

f = f && (! vars || vars);

f = f && (! vars || vars);

статичен bool Fun53(bool vars)

f = f && ((променливи == променливи) || (променливи == променливи));

f = f && ((променливи == променливи) || (променливи == променливи));

f = f && ((променливи == променливи) || (променливи == променливи));

f = f && ((променливи == променливи) || (променливи == променливи));

f = f && ((променливи == променливи) || (променливи == променливи));

f = f && ((променливи == променливи) || (променливи == променливи));

f = f && (!((vars == vars) || (vars == vars)));

Ето как изглеждат резултатите от решението за тази програма:

10 задачи за самостоятелна работа

1. Кои от трите функции са еквивалентни:
   1. (X → Y) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄Y
2. Даден е фрагмент от таблицата на истината:

X 1	X 2	X 3	X 4	Е
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

На коя от трите функции отговаря този фрагмент:

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
4. Журито се състои от трима души. Решението е взето, ако за него гласува председателят на журито, подкрепено от поне един от членовете на журито. В противен случай не се взема решение. Конструирайте логическа функция, която формализира процеса на вземане на решение.
5. X печели над Y, ако четири хвърляния на монети доведат до глави три пъти. Дефинирайте логическа функция, която описва изплащането на X.
6. Думите в изречението се номерират от едно. Едно изречение се счита за правилно конструирано, ако са изпълнени следните правила:
   1. Ако дума с четен номер завършва с гласна, тогава следващата дума, ако съществува, трябва да започва с гласна.
   2. Ако дума с нечетен номер завършва на съгласна, то следващата дума, ако има такава, трябва да започва със съгласна и да завършва с гласна.
      Кои от следните изречения са правилно построени:
   3. Мама изми Маша със сапун.
   4. Лидерът винаги е модел.
   5. Истината е добра, но щастието е по-добро.
7. Колко решения има уравнението:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Избройте всички решения на уравнението:
   (a → b) → c = 0
9. Колко решения има следната система от уравнения:
   X 0 → X 1 ˄ X 1 → X 2 = 1
   X 2 → X 3 ˄ X 3 → X 4 = 1
   X 5 → X 6 ˄ X 6 → X 7 = 1
   X 7 → X 8 ˄ X 8 → X 9 = 1
   X 0 → X 5 = 1
10. Колко решения има уравнението:
    ((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

Отговори на проблеми:

1. Функциите b и c са еквивалентни.
2. Фрагментът съответства на функция b.
3. Нека логическата променлива P приеме стойност 1, когато председателят на журито гласува „за” решението. Променливите M 1 и M 2 представляват мненията на членовете на журито. Логическата функция, която определя вземането на положително решение, може да бъде написана по следния начин:
   P ˄ (M 1 ˅ M 2)
4. Нека логическата променлива P i приеме стойност 1, когато i-тото хвърляне на монета падне върху глави. Логическата функция, която определя изплащането X, може да бъде написана по следния начин:
   ¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
   (¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
   (¬P 3 ˄ ¬P 4))
5. Изречение b.
6. Уравнението има 3 решения: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

В края на годината се оказа, че само едно от трите предположения е вярно. Кои подразделения са на печалба в края на годината?

Решение. Нека запишем предположенията от условията на проблема под формата на логически твърдения: „Получаването на печалба от раздел Б не е необходимо условие за получаване на

печалба по дивизия A ": F 1 (A, B, C) = A → B

„Получаването на печалба от поне едно подразделение B и C не е достатъчно, за да може подразделение A да реализира печалба“: F 2 (A, B, C) = (B + C) → A

„Дивизии A и B няма да реализират печалба едновременно“: F 3 (A, B, C) = A B

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

1) F 1F 2F 3

2) F 1F 2F 3

3) F 1F 2F 3

1) (A→ B) ((B+ C) → A) (A↔ B) = A B(B C+ A) (A B+ A B) = 0

2) (A→ B) ((B+ C) → A) (A↔ B) = (A+ B) (A B+ A C) (A B+ A B) = A B C

3) (A→ B) ((B+ C) → A) (A B) = (A+ B) (B C+ A) (A B+ A B) = 0

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

									А=0
	F1 F2 F3 = A B C= 1
									ако и само ако B = 0.
									C=1

Следователно дивизия C ще получи печалба, но дивизии A и B няма да получат печалба.

Решаване на логически уравнения

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

Намерете корена на логическото уравнение: (A + B)(X AB) = B + X → A.

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

F1 (A, B, X) = (A+ B)(X AB)

					A+B	(A+ B)(X AB)	F 1 (A, B, X)

F2 (A, B, X) = B+ X→ A

			X → A							F 2 (A, B, X)
					X → A			X → A

Нека да сравним получените таблици на истината и да изберем онези редове, в които стойностите на F 1 (A, B, X) и F 2 (A, B, X) съвпадат.

			F 1 (A, B, X)	F 2 (A, B, X)

Нека пренапишем само избраните редове, оставяйки само колоните с аргументи. Нека разгледаме променливата X като функция на A и B.

Очевидно X = B → A.

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

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

F1 = (A+ B)(X AB) = A+ B+ (X↔ AB) = A B+ X A B+ X A+ X B

F1 = (A+ B)(X AB) = (A+ B)(X A+ X B+ X A B) = X A B+ X A B+ X A B

F2 = B+ X→ A= B(X→ A) = B(X+ A) = X B+ A B F2 = B+ X→ A= B+ X+ A= B+ X A

Нека заменим знака за равенство в нашето логическо уравнение със знак за еквивалентност:

F1 ↔ F2 = F1 F2 + F1 F2 = (A B+ X A B+ X A+ X B) (X B+ A B) +

+ (X A B+ X A B+ X A B) (B+ X A) =

= (X A B+ X B+ X A B) + (X A B+ X A B) =

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

X(A B) + X(B+ AB) = X(A B) + X(B+ A) =

Тогава нека означим T = A B

X T+ X T= X↔ T.

Следователно, за да има решение на едно логическо уравнение: X = A B = B + A = B → A.

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

С развитието на компютърните технологии математическата логика се оказа тясно свързана с въпросите на проектирането и програмирането на компютърните технологии. Алгебрата на логиката намери широко приложение първоначално в развитието релеен контактсхеми Първо фундаментални изследвания, който насочи вниманието на инженерите, занимаващи се с компютърен дизайн, към възможността за анализ на електрически вериги с помощта на булева алгебра, през декември 1938 г. беше публикувана статия на американеца Клод Шанън „Символичен анализ на релейни вериги“. След тази статия компютърният дизайн не може да бъде направен без използването на булева алгебра.

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

Серийно свързване на контакти

Паралелно свързване на контакти

Нека съставим таблица на зависимостите на състоянието на веригите от всички възможни състояния на контактите. Нека въведем следните обозначения: 1 – контактът е затворен, има ток във веригата; 0 – контактът е отворен, няма ток във веригата.

		Състояние на веригата	Състояние на веригата с паралел
		серийна връзка	връзка

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

Логическата операция на инверсия се осъществява чрез контактната верига на електромагнитно реле, чийто принцип се изучава в училищен курс по физика. Контактът x е отворен, когато x е затворен и обратно.

Използването на релейни контактни елементи за конструиране на логически схеми на компютри не се оправда поради ниската надеждност, големите размери, високата консумация на енергия и ниската производителност. Появата на електронни устройства (вакуумни и полупроводникови) създаде възможност за конструиране на логически елементи със скорости от 1 милион превключвания в секунда и по-високи. Полупроводниковите логически елементи работят в режим на превключване, подобно на електромагнитно реле. Цялата теория, представена за контактни вериги, се пренася върху полупроводникови елементи. Логическите елементи на полупроводниците се характеризират не със състоянието на контактите, а с наличието на сигнали на входа и изхода.

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

Инвертор - реализира операцията на отрицание или инверсия. U

инверторът има един вход и един изход. Появява се изходният сигнал

когато няма такъв на входа и обратно.

конюнктор -

X1 X2 ... Xn

изпълнява операцията конюнкция.

При конюнктора

един изход и поне два входа. Сигнал включен

се появява в изхода, ако и само ако

всички входове са сигнализирани.

X2 + ... Xn

Disjunctor - реализира операцията disjunctor. U

дизюнктор има един изход и поне два

Изходният сигнал не се появява тогава и само ако

когато не се подават сигнали към всички входове.

	Изграждане	функционален
F(X, Y, Z) = X(Y+ Z)
			X+Z

диаграма, съответстваща на функцията:

&F(X, Y, Z)

Решаване на задачи с помощта на конюнктивен нормален

И дизюнктивно-нормаленформи

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

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

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

аргументи, а стойността е 0 за всички останали. Пример: x 1 x 2 x 3 x 4.

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

Пример: x 1 + x 2 + x 3.

Функция в дизюнктивна нормална форма(DNF) е логическата сума на минтермите.

Пример: x 1x 2+ x 1x 2+ x 1x 2x 3.

Съединителна нормална форма(CNF) е логически продукт на елементарни дизюнкции (макстерми).

Пример: (x 1+ x 2+ x 3) (x 1+ x 2) .

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

Пример: x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3

Перфектен конюнктив нормална форма се нарича CNF, във всеки макстерм от който присъстват всички променливи или техните отрицания.

Пример: (x 1+ x 2+ x 3) (x 1+ x 2+ x 3)

Написване на логическа функция от таблица

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

			f(x1, x2, x3)

Функциите G0, G1, G4, G5, G7 са минтерми (виж дефиницията). Всяка от тези функции е продукт на три променливи или техни обратни и приема стойност 1 само в една ситуация. Вижда се, че за да получим 1 в стойността на функцията f, е необходим един минтерм. Следователно броят на минтермите, които съставят SDNF на тази функция, е равен на броя на единиците в стойността на функцията: f= G0+G1+G4+G5+G7. Така SDNF има формата:

f (x 1, x 2, x 3) = x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3+ x 1x 2x 3.

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

f (x 1, x 2, x 3) = (x 1+ x 2+ x 3) (x 1+ x 2+ x 3) (x 1+ x 2+ x 3) .

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

Алгоритъм за конструиране на SDNF с помощта на таблица на истината

Дадена е таблица на истинността на някаква функция. За да изградите SDNF, трябва да изпълните следната последователност от стъпки:

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

2. За всеки такъв ред задайте връзка на всички аргументи или техните инверсии (minterm). В този случай аргументът със стойност 0 се включва в минтерма с отрицание, а стойността 1 се включва без отрицание.

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

Алгоритъм за конструиране на SCNF с помощта на таблица на истината

Дадена е таблица на истинността на някаква функция. За да изградите SKNF, трябва да изпълните следната последователност от стъпки:

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

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

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

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

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

			F(A, B, C)

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

F(A, B, C) = (A+ B+ C) (A+ B+ C)

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

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

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

1. Трима учители избират задачи за олимпиадата. Има няколко задачи за избор. За всяка задача всеки учител изразява своето мнение: лесна (0) или трудна (1) задача. Една задача се включва в олимпиадната задача, ако поне двама учители я оценят като трудна, но ако и тримата учители я считат за трудна, тогава такава задача не се включва в олимпиадната задача като твърде трудна. Направете логическа схема на устройство, което ще изведе 1, ако задачата е включена в задачата за олимпиада, и 0, ако не е включена.

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

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

Ние изграждаме SDNF. F(A, B, C) = ABC+ ABC+ ABC

Сега изграждаме логическа диаграма на тази функция.

B&1F(A,B,C)

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

И така, имаме три превключвателя, които трябва да използваме, за да включваме и изключваме светлината. Всеки ключ има две състояния: нагоре (0) и надолу (1). Да приемем, че ако и трите ключа са в позиция 0, светлините във входа са изключени. След това, когато преместите някой от трите ключа на позиция 1, лампата във входа трябва да светне. Очевидно, когато преместите който и да е друг ключ в позиция 1, светлината във входа ще се изключи. Ако третият ключ се превключи на позиция 1, лампата във входа ще светне. Изграждаме таблица на истината.

Тогава F(A, B, C) = ABC+ ABC+ ABC+ ABC.

	3. Промяна на условието			стойности на логическа функция			F(A, B, C) = C→		A+B
	промяна на аргументи B и C едновременно е равно на:
		A → (B C)						(B C) → A
					A(B C)
	4) (B C) → A				A → (B C)

Забележка. За да разрешите успешно този проблем, запомнете следните логически формули:

x → y= x+ y x y= x y+ x y

x ↔ y= x y+ x y

Дадена ни е логическа функция от три променливи F 1 (A, B, C) = C → A + B = C + A B.

Нека променим променливите B и C едновременно: F 2 (A, B, C) = F 1 (A, B, C) = C + A B. Нека изградим таблици на истината за тези две функции:

Нека анализираме получената таблица. От осемте реда на таблицата само в два (2-ри и 3-ти) функцията не променя стойността си. Забележете, че в тези редове променлива A не обръща стойността си, но променливи B и C го правят.

Ние изграждаме SKNF функции, използвайки тези редове:

F3 (A, B, C) = (A+ B+ C) (A+ B C) = A+ AB+ AC+ AB+ BC+ AC+ B C= .

A+ (B↔ C) = A+ B C= (B C) → A

Следователно желаният отговор е 4.

4. Условие за промяна на стойността на логическа функция F (A, B, C) = C + AB при едновременна промяна на аргументите A и B е равно на:

1) C+ (A B)

C+(A B)

C(A B)

4) C(A B)

C → (A B)

F 1 (A,B,C)=

C+AB

F 2 (A, B, C) = F 1 (

C )= A

Изграждаме таблица на истината.

Нека анализираме получената таблица. От осемте реда на таблицата само в два (1-ви и 7-ми) функцията променя стойността си. Моля, обърнете внимание, че в тези редове променливата C не променя стойността си, но променливите A и B го правят.

Ние изграждаме SDNF функции, използвайки тези редове:

F3 (A, B, C) = A B C+ A B C= C(A B+ A B) = C(A↔ B) = C+ (A B)

Следователно желаният отговор е 2.

Използвана литература

1. Шапиро С.И. Решаване на логически и игрови задачи(логически и психологически изследвания). – М.: Радио и съобщения, 1984. – 152 с.

2. Шоломов Л.А. Основи на теорията на дискретните логически и изчислителни устройства. – М.: Наука. гл. изд. физически - мат. лит., 1980. - 400 с.

3. Пухалски Г.И., Новоселцева Т.Я. Проектиране на дискретни устройства на интегрални схеми: Наръчник. – М.: Радио и съобщения, 1990.

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

Задача:Решете система от логически уравнения:

Нека помислим метод на редукция до едно уравнение . Този метод включва трансформиране на логически уравнения, така че техните десни части да са равни на стойността на истината (т.е. 1). За да направите това, използвайте операцията за логическо отрицание. След това, ако уравненията съдържат сложни логически операции, ги заместваме с основни: „И“, „ИЛИ“, „НЕ“. Следващата стъпка е да комбинирате уравненията в едно, еквивалентно на системата, като използвате логическата операция „И“. След това трябва да трансформирате полученото уравнение въз основа на законите на логическата алгебра и да получите конкретно решение на системата.

Решение 1:Приложете инверсия към двете страни на първото уравнение:

Нека си представим извода чрез основните операции „ИЛИ“ и „НЕ“:

Тъй като левите части на уравненията са равни на 1, можем да ги комбинираме с помощта на операцията „И“ в едно уравнение, което е еквивалентно на оригиналната система:

Отваряме първата скоба според закона на Де Морган и трансформираме получения резултат:

Полученото уравнение има едно решение: A =0, B=0 и C=1.

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

Решение 2:Нека създадем таблица на истината за системата:

0	0	1	1	0	1

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

начин разграждане . Идеята е да се фиксира стойността на една от променливите (да се зададе равна на 0 или 1) и по този начин да се опростят уравненията. След това можете да коригирате стойността на втората променлива и т.н.

Решение 3:Нека A = 0, тогава:

От първото уравнение получаваме B = 0, а от второто - C = 1. Решение на системата: A = 0, B = 0 и C = 1.

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

Задача:Колко решения има уравнението (A → B) + (C → D) = 1? Където A, B, C, D са логически променливи.

Решение:Нека въведем нови променливи: X = A → B и Y = C → D. Като се вземат предвид новите променливи, уравнението ще бъде написано като: X + Y = 1.

Дизюнкцията е вярна в три случая: (0;1), (1;0) и (1;1), докато X и Y са импликации, тоест тя е вярна в три случая и невярна в един. Следователно случаят (0;1) ще съответства на три възможни комбинации от параметри. Случай (1;1) – ще съответства на девет възможни комбинации от параметри на първоначалното уравнение. И така, общо възможни решенияот това уравнение 3+9=15.

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

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

Дадената система от уравнения е еквивалентна на уравнението:

(х 1 → х 2 )*(х 2 → х 3 )*…*(x m -1 → x m) = 1.

Да приемем, че х 1 – е вярно, тогава от първото уравнение получаваме това х 2 също вярно, от второто - х 3 =1 и така нататък, докато x m= 1. Това означава, че множеството (1; 1; …; 1) от m единици е решение на системата. Нека сега х 1 =0, тогава от първото уравнение имаме х 2 =0 или х 2 =1.

Кога х 2 true, получаваме, че останалите променливи също са true, т.е. множеството (0; 1; ...; 1) е решение на системата. При х 2 =0 получаваме това х 3 =0 или х 3 = и така нататък. Продължавайки към последната променлива, откриваме, че решенията на уравнението са следните набори от променливи (m +1 решение, всяко решение съдържа m стойности на променливите):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Този подход е добре илюстриран чрез конструиране на двоично дърво. Броят на възможните решения е броят на различните клони на построеното дърво. Лесно се вижда, че то е равно на m +1.

	Дърво	Брой решения
х 1
х 2
х 3
		…

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

Нека пренапишем системата от уравнения във формата:

И нека създадем таблица на истината отделно за едно уравнение:

х 1	х 2	(x 1 → x 2)

Нека създадем таблица на истината за две уравнения:

х 1	х 2	х 3	x 1 → x 2	x 2 → x 3	(x 1 → x 2) * (x 2 → x 3)

Цел на услугата. Онлайн калкулаторът е предназначен за конструиране на таблица на истинност за логически израз.
Таблица на истината – таблица, съдържаща всички възможни комбинации от входни променливи и съответните им изходни стойности.
Таблицата на истината съдържа 2n реда, където n е броят на входните променливи, а n+m са колони, където m са изходните променливи.

Инструкции. Когато въвеждате от клавиатурата, използвайте следните конвенции:

Булев израз:

Извеждане на междинни таблици за таблицата на истината
Изграждане на СКНФ
Изграждане на SDNF
Конструкция на полинома на Жегалкин
Построяване на картата на Veitch-Karnaugh
Минимизиране на булева функция

Например, логическият израз abc+ab~c+a~bc трябва да бъде въведен така: a*b*c+a*b=c+a=b*c
За да въведете данни под формата на логическа диаграма, използвайте тази услуга.

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

1. Вместо символа v (дизюнкция, ИЛИ), използвайте знака +.
2. Не е необходимо да се указва обозначение на функция преди логическа функция. Например, вместо F(x,y)=(x|y)=(x^y) трябва просто да въведете (x|y)=(x^y) .
3. Максималният брой променливи е 10.

Проектирането и анализът на компютърни логически схеми се извършва с помощта на специален клон на математиката - логическата алгебра. В алгебрата на логиката могат да се разграничат три основни логически функции: „НЕ“ (отрицание), „И“ (конюнкция), „ИЛИ“ (дизюнкция).
За да се създаде всяко логическо устройство, е необходимо да се определи зависимостта на всяка от изходните променливи от съществуващите входни променливи; тази зависимост се нарича превключваща функция или функция на логическата алгебра.
Функция на логическата алгебра се нарича напълно дефинирана, ако са дадени всички 2n от нейните стойности, където n е броят на изходните променливи.
Ако не всички стойности са дефинирани, функцията се нарича частично дефинирана.
Едно устройство се нарича логическо, ако неговото състояние е описано с помощта на функция на логическата алгебра.
Следните методи се използват за представяне на функция на логическата алгебра:
В алгебрична форма можете да изградите схема на логическо устройство, използвайки логически елементи.


Фигура 1 - Диаграма на логическо устройство

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

Операция НЕ - логическо отрицание (инверсия)

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

• ако оригиналният израз е верен, тогава резултатът от неговото отрицание ще бъде фалшив;
• ако оригиналният израз е фалшив, тогава резултатът от неговото отрицание ще бъде верен.

Следните конвенции НЕ се приемат за операцията за отрицание:
не A, Ā, не A, ¬A, !A
Резултатът от операцията за отрицание НЕ се определя от следната таблица на истината:

А	не А
0	1
1	0

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

Операция ИЛИ - логическо събиране (дизюнкция, обединение)

Логическата операция ИЛИ изпълнява функцията на комбиниране на две твърдения, които могат да бъдат прост или сложен логически израз. Изявленията, които са отправните точки за логическа операция, се наричат ​​аргументи. Резултатът от операцията ИЛИ е израз, който ще бъде верен тогава и само ако поне един от оригиналните изрази е верен.
Използвани обозначения: A или B, A V B, A или B, A||B.
Резултатът от операцията ИЛИ се определя от следната таблица на истината:
Резултатът от операцията OR е true, когато A е true, или B е true, или и A, и B са true, и false, когато аргументите A и B са false.

Операция И - логическо умножение (конюнкция)

Логическата операция И изпълнява функцията на пресичане на две твърдения (аргументи), които могат да бъдат както прост, така и сложен логически израз. Резултатът от операцията И е израз, който ще бъде верен тогава и само ако и двата оригинални израза са верни.
Използвани обозначения: A и B, A Λ B, A & B, A и B.
Резултатът от операцията И се определя от следната таблица на истината:

А	б	А и Б
0	0	0
0	1	0
1	0	0
1	1	1

Резултатът от операцията И е верен тогава и само ако изявления А и Б са верни и грешни във всички останали случаи.

Операция “АКО-ТОГАВА” - логическо следствие (импликация)

Тази операция свързва два прости логически израза, от които първият е условие, а вторият е следствие от това условие.
Използвани обозначения:
ако A, тогава B; A води до B; ако A тогава B; A→B.
Таблица на истината:

А	б	А → Б
0	0	1
0	1	1
1	0	0
1	1	1

Резултатът от операцията на импликация е неверен само ако предпоставка A е вярна и заключение B (следствие) е невярно.

Операция „A ако и само ако B“ (еквивалентност, еквивалентност)

Използвано обозначение: A ↔ B, A ~ B.
Таблица на истината:

А	б	A↔B
0	0	1
0	1	0
1	0	0
1	1	1

Операция „Добавяне по модул 2“ (XOR, изключителна или стриктна дизюнкция)

Използвана нотация: A XOR B, A ⊕ B.
Таблица на истината:

А	б	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Резултатът от операцията за еквивалентност е верен само ако A и B са едновременно true или false.

Приоритет на логическите операции

• Действия в скоби
• Инверсия
• Съюз (&)
• Дизюнкция (V), Изключително ИЛИ (XOR), сума по модул 2
• Извод (→)
• Еквивалентност (↔)

Перфектна дизюнктивна нормална форма

Перфектна дизюнктивна нормална форма на формула(SDNF) е еквивалентна формула, която е дизюнкция на елементарни конюнкции и има следните свойства:

1. Всеки логически член на формулата съдържа всички променливи, включени във функцията F(x 1,x 2,...x n).
2. Всички логически членове на формулата са различни.
3. Нито един логически термин не съдържа променлива и нейното отрицание.
4. Нито един логически термин във формула не съдържа една и съща променлива два пъти.

SDNF може да се получи или с помощта на таблици на истината, или с помощта на еквивалентни трансформации.
За всяка функция SDNF и SCNF са уникално дефинирани до пермутация.

Перфектен конюнктив нормална форма

Перфектна конюнктивна нормална форма на формула (SCNF)Това е еквивалентна на нея формула, която е конюнкция на елементарни дизюнкции и удовлетворява свойствата:

1. Всички елементарни дизюнкции съдържат всички променливи, включени във функцията F(x 1 ,x 2 ,...x n).
2. Всички елементарни дизюнкции са различни.
3. Всяка елементарна дизюнкция съдържа променлива веднъж.
4. Нито една елементарна дизюнкция не съдържа променлива и нейното отрицание.

Използването на уравнения е широко разпространено в живота ни. Те се използват в много изчисления, изграждане на конструкции и дори спорт. Човекът е използвал уравнения в древни времена и оттогава употребата им само се е увеличила. В математиката има определени проблеми, които се занимават с пропозиционалната логика. За да разрешите този вид уравнение, трябва да имате определено количество знания: познаване на законите на пропозиционалната логика, познаване на таблиците на истинност на логическите функции на 1 или 2 променливи, методи за преобразуване на логически изрази. Освен това трябва да знаете следните свойства на логическите операции: конюнкция, дизюнкция, инверсия, импликация и еквивалентност.

Всяка логическа функция на \variables - \може да бъде определена от таблица на истината.

Нека решим няколко логически уравнения:

\[\rightharpoondown X1\vee X2=1 \]

\[\rightharpoondown X2\vee X3=1\]

\[\rightharpoondown X3\vee X4=1 \]

\[\rightharpoondown X9\vee X10=1\]

Нека започнем решението с \[X1\] и определим какви стойности може да приеме тази променлива: 0 и 1. След това ще разгледаме всяка от горните стойности и ще видим какво може да бъде \[X2.\].

Както се вижда от таблицата, нашето логическо уравнение има 11 решения.

Къде мога да реша онлайн логическо уравнение?

Можете да решите уравнението на нашия уебсайт https://site. Безплатен онлайн решаващ инструмент ще ви позволи да решите уравнението онлайн всякаквисложност за секунди. Всичко, което трябва да направите, е просто да въведете данните си в решаващия инструмент. Можете също да гледате видео инструкции и да научите как да решите уравнението на нашия уебсайт. И ако все още имате въпроси, можете да ги зададете в нашата група VKontakte http://vk.com/pocketteacher. Присъединете се към нашата група, винаги се радваме да ви помогнем.