🗊Презентация Propositional logic

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Propositional logic, слайд №1Propositional logic, слайд №2Propositional logic, слайд №3Propositional logic, слайд №4Propositional logic, слайд №5Propositional logic, слайд №6Propositional logic, слайд №7Propositional logic, слайд №8Propositional logic, слайд №9Propositional logic, слайд №10Propositional logic, слайд №11Propositional logic, слайд №12Propositional logic, слайд №13Propositional logic, слайд №14Propositional logic, слайд №15Propositional logic, слайд №16Propositional logic, слайд №17Propositional logic, слайд №18Propositional logic, слайд №19Propositional logic, слайд №20Propositional logic, слайд №21Propositional logic, слайд №22Propositional logic, слайд №23Propositional logic, слайд №24Propositional logic, слайд №25Propositional logic, слайд №26Propositional logic, слайд №27Propositional logic, слайд №28Propositional logic, слайд №29Propositional logic, слайд №30Propositional logic, слайд №31Propositional logic, слайд №32Propositional logic, слайд №33Propositional logic, слайд №34Propositional logic, слайд №35Propositional logic, слайд №36Propositional logic, слайд №37Propositional logic, слайд №38Propositional logic, слайд №39Propositional logic, слайд №40Propositional logic, слайд №41Propositional logic, слайд №42Propositional logic, слайд №43Propositional logic, слайд №44Propositional logic, слайд №45Propositional logic, слайд №46Propositional logic, слайд №47Propositional logic, слайд №48Propositional logic, слайд №49Propositional logic, слайд №50Propositional logic, слайд №51Propositional logic, слайд №52Propositional logic, слайд №53Propositional logic, слайд №54Propositional logic, слайд №55Propositional logic, слайд №56Propositional logic, слайд №57Propositional logic, слайд №58Propositional logic, слайд №59Propositional logic, слайд №60Propositional logic, слайд №61Propositional logic, слайд №62Propositional logic, слайд №63Propositional logic, слайд №64Propositional logic, слайд №65Propositional logic, слайд №66Propositional logic, слайд №67Propositional logic, слайд №68Propositional logic, слайд №69Propositional logic, слайд №70Propositional logic, слайд №71Propositional logic, слайд №72Propositional logic, слайд №73Propositional logic, слайд №74Propositional logic, слайд №75Propositional logic, слайд №76Propositional logic, слайд №77Propositional logic, слайд №78Propositional logic, слайд №79Propositional logic, слайд №80Propositional logic, слайд №81Propositional logic, слайд №82Propositional logic, слайд №83Propositional logic, слайд №84Propositional logic, слайд №85Propositional logic, слайд №86Propositional logic, слайд №87Propositional logic, слайд №88Propositional logic, слайд №89Propositional logic, слайд №90Propositional logic, слайд №91Propositional logic, слайд №92Propositional logic, слайд №93Propositional logic, слайд №94Propositional logic, слайд №95Propositional logic, слайд №96Propositional logic, слайд №97Propositional logic, слайд №98Propositional logic, слайд №99Propositional logic, слайд №100Propositional logic, слайд №101Propositional logic, слайд №102Propositional logic, слайд №103Propositional logic, слайд №104
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Propositional logic. Доклад-сообщение содержит 104 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Propositional logic Irina Prosvirnina Propositions Compound propositions Conditional statements Truth tables of compound propositions Tautologies and contradictions Logical equivalences Propositional satisfiability Satisfiability problem
Описание слайда:
Propositional logic Irina Prosvirnina Propositions Compound propositions Conditional statements Truth tables of compound propositions Tautologies and contradictions Logical equivalences Propositional satisfiability Satisfiability problem

Слайд 2


Propositions Our discussion begins with an introduction to the basic building blocks of logic – propositions. Definition 1 A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both.
Описание слайда:
Propositions Our discussion begins with an introduction to the basic building blocks of logic – propositions. Definition 1 A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both.

Слайд 3


Propositions Example 1 All the following declarative sentences are propositions. 1. Minsk is the capital of Belarus. 2. Toronto is the capital of Canada. 3. 1+1=2. 4. 2+2=3. Propositions 1 and 3 are true, whereas 2 and 4 are false.
Описание слайда:
Propositions Example 1 All the following declarative sentences are propositions. 1. Minsk is the capital of Belarus. 2. Toronto is the capital of Canada. 3. 1+1=2. 4. 2+2=3. Propositions 1 and 3 are true, whereas 2 and 4 are false.

Слайд 4


Propositions Example 2 Consider the following sentences. 1. What time is it? 2. Read this carefully. 3. . 4. . Sentences 1 and 2 are not propositions because they are not declarative sentences. Sentences 3 and 4 are not propositions because they are neither true nor false. Note that each of sentences 3 and 4 can be turned into a proposition if we assign values to the variables.
Описание слайда:
Propositions Example 2 Consider the following sentences. 1. What time is it? 2. Read this carefully. 3. . 4. . Sentences 1 and 2 are not propositions because they are not declarative sentences. Sentences 3 and 4 are not propositions because they are neither true nor false. Note that each of sentences 3 and 4 can be turned into a proposition if we assign values to the variables.

Слайд 5


Propositions We use letters to denote propositional variables (or statement variables), that is, variables that represent propositions, just as letters are used to denote numerical variables. The conventional letters used for propositional variables are ,... . The truth value of a proposition is true, denoted by , if it is a true proposition, and the truth value of a proposition is false, denoted by , if it is a false proposition.
Описание слайда:
Propositions We use letters to denote propositional variables (or statement variables), that is, variables that represent propositions, just as letters are used to denote numerical variables. The conventional letters used for propositional variables are ,... . The truth value of a proposition is true, denoted by , if it is a true proposition, and the truth value of a proposition is false, denoted by , if it is a false proposition.

Слайд 6


Propositions The area of logic that deals with propositions is called the propositional calculus or propositional logic. It was first developed systematically by the Greek philosopher Aristotle more than 2300 years ago.
Описание слайда:
Propositions The area of logic that deals with propositions is called the propositional calculus or propositional logic. It was first developed systematically by the Greek philosopher Aristotle more than 2300 years ago.

Слайд 7


Compound propositions We now turn our attention to methods for producing new propositions from those that we already have. These methods were discussed by the English mathematician George Boole in 1854 in his book The Laws of Thought.
Описание слайда:
Compound propositions We now turn our attention to methods for producing new propositions from those that we already have. These methods were discussed by the English mathematician George Boole in 1854 in his book The Laws of Thought.

Слайд 8


Compound propositions Many mathematical statements are constructed by combining one or more propositions. New propositions, called compound propositions, are formed from existing propositions using logical operators.
Описание слайда:
Compound propositions Many mathematical statements are constructed by combining one or more propositions. New propositions, called compound propositions, are formed from existing propositions using logical operators.

Слайд 9


The negation of a proposition Definition 2 Let p be a proposition. The negation of p, denoted by p (also denoted by p), is the statement “It is not the case that p.” The proposition p is read “not p.” The truth value of the negation of p, p, is the opposite of the truth value of p.
Описание слайда:
The negation of a proposition Definition 2 Let p be a proposition. The negation of p, denoted by p (also denoted by p), is the statement “It is not the case that p.” The proposition p is read “not p.” The truth value of the negation of p, p, is the opposite of the truth value of p.

Слайд 10


The negation of a proposition
Описание слайда:
The negation of a proposition

Слайд 11


The negation of a proposition Example 3 Find the negation of the proposition “Vandana’s smartphone has at least 32GB of memory” and express this in simple English. Solution The negation is “It is not the case that Vandana’s smartphone has at least 32GB of memory.” This negation can also be expressed as “Vandana’s smartphone does not have at least 32GB of memory” or even more simply as “Vandana’s smartphone has less than 32GB of memory.”
Описание слайда:
The negation of a proposition Example 3 Find the negation of the proposition “Vandana’s smartphone has at least 32GB of memory” and express this in simple English. Solution The negation is “It is not the case that Vandana’s smartphone has at least 32GB of memory.” This negation can also be expressed as “Vandana’s smartphone does not have at least 32GB of memory” or even more simply as “Vandana’s smartphone has less than 32GB of memory.”

Слайд 12


The conjunction of two propositions Definition 3 Let p and q be propositions. The conjunction of p and q, denoted by p∧q, is the proposition “p and q”. The conjunction p∧q is true when both p and q are true and is false otherwise.
Описание слайда:
The conjunction of two propositions Definition 3 Let p and q be propositions. The conjunction of p and q, denoted by p∧q, is the proposition “p and q”. The conjunction p∧q is true when both p and q are true and is false otherwise.

Слайд 13


The conjunction of two propositions
Описание слайда:
The conjunction of two propositions

Слайд 14


The conjunction of two propositions Example 4 Find the conjunction of the propositions p and q where p is the proposition “Rebecca’s PC has more than 16 GB free hard disk space” and q is the proposition “The processor in Rebecca’s PC runs faster than 1 GHz.”
Описание слайда:
The conjunction of two propositions Example 4 Find the conjunction of the propositions p and q where p is the proposition “Rebecca’s PC has more than 16 GB free hard disk space” and q is the proposition “The processor in Rebecca’s PC runs faster than 1 GHz.”

Слайд 15


The conjunction of two propositions Solution The conjunction of these propositions, p∧q, is the proposition “Rebecca’s PC has more than 16 GB free hard disk space, and the processor in Rebecca’s PC runs faster than 1 GHz.” This conjunction can be expressed more simply as “Rebecca’s PC has more than 16 GB free hard disk space, and its processor runs faster than 1 GHz.” For this conjunction to be true, both conditions given must be true. It is false, when one or both of these conditions are false.
Описание слайда:
The conjunction of two propositions Solution The conjunction of these propositions, p∧q, is the proposition “Rebecca’s PC has more than 16 GB free hard disk space, and the processor in Rebecca’s PC runs faster than 1 GHz.” This conjunction can be expressed more simply as “Rebecca’s PC has more than 16 GB free hard disk space, and its processor runs faster than 1 GHz.” For this conjunction to be true, both conditions given must be true. It is false, when one or both of these conditions are false.

Слайд 16


The disjunction of two propositions Definition 4 Let p and q be propositions. The disjunction of p and q, denoted by p∨q, is the proposition “p or q”. The disjunction p∨q is false when both p and q are false and is true otherwise.
Описание слайда:
The disjunction of two propositions Definition 4 Let p and q be propositions. The disjunction of p and q, denoted by p∨q, is the proposition “p or q”. The disjunction p∨q is false when both p and q are false and is true otherwise.

Слайд 17


The disjunction of two propositions
Описание слайда:
The disjunction of two propositions

Слайд 18


The disjunction of two propositions Example 5 Find the disjunction of the propositions p and q where p is the proposition “Rebecca’s PC has more than 16 GB free hard disk space” and q is the proposition “The processor in Rebecca’s PC runs faster than 1 GHz.”
Описание слайда:
The disjunction of two propositions Example 5 Find the disjunction of the propositions p and q where p is the proposition “Rebecca’s PC has more than 16 GB free hard disk space” and q is the proposition “The processor in Rebecca’s PC runs faster than 1 GHz.”

Слайд 19


The disjunction of two propositions Solution The disjunction of p and q, p∨q, is the proposition “Rebecca’s PC has at least 16 GB free hard disk space, or the processor in Rebecca’s PC runs faster than 1 GHz.” This proposition is true when Rebecca’s PC has at least 16 GB free hard disk space, when the PC’s processor runs faster than 1 GHz, and when both conditions are true. It is false when both of these conditions are false, that is, when Rebecca’s PC has less than 16 GB free hard disk space and the processor in her PC runs at 1 GHz or slower.
Описание слайда:
The disjunction of two propositions Solution The disjunction of p and q, p∨q, is the proposition “Rebecca’s PC has at least 16 GB free hard disk space, or the processor in Rebecca’s PC runs faster than 1 GHz.” This proposition is true when Rebecca’s PC has at least 16 GB free hard disk space, when the PC’s processor runs faster than 1 GHz, and when both conditions are true. It is false when both of these conditions are false, that is, when Rebecca’s PC has less than 16 GB free hard disk space and the processor in her PC runs at 1 GHz or slower.

Слайд 20


The exclusive or The use of the connective or in a disjunction corresponds to one of the two ways the word or is used in English, namely, as an inclusive or. A disjunction is true when at least one of the two propositions is true.
Описание слайда:
The exclusive or The use of the connective or in a disjunction corresponds to one of the two ways the word or is used in English, namely, as an inclusive or. A disjunction is true when at least one of the two propositions is true.

Слайд 21


The exclusive or On the other hand, we are using the exclusive or when we say “Students who have taken calculus or computer science, but not both, can enroll in this class.” Here, we mean that students who have taken both calculus and a computer science course cannot take the class. Only those who have taken exactly one of the two courses can take the class.
Описание слайда:
The exclusive or On the other hand, we are using the exclusive or when we say “Students who have taken calculus or computer science, but not both, can enroll in this class.” Here, we mean that students who have taken both calculus and a computer science course cannot take the class. Only those who have taken exactly one of the two courses can take the class.

Слайд 22


The exclusive or Definition 5 Let p and q be propositions. The exclusive or of p and q, denoted by pq, is the proposition that is true when exactly one of p and q is true and is false otherwise.
Описание слайда:
The exclusive or Definition 5 Let p and q be propositions. The exclusive or of p and q, denoted by pq, is the proposition that is true when exactly one of p and q is true and is false otherwise.

Слайд 23


The exclusive or
Описание слайда:
The exclusive or

Слайд 24


Conditional statements Definition 6 Let and be propositions. The conditional statement is the proposition “if , then ”. The conditional statement is false when is true and is false, and true otherwise. In the conditional statement , is called the hypothesis (or antecedent or premise) and is called the conclusion (or consequence).
Описание слайда:
Conditional statements Definition 6 Let and be propositions. The conditional statement is the proposition “if , then ”. The conditional statement is false when is true and is false, and true otherwise. In the conditional statement , is called the hypothesis (or antecedent or premise) and is called the conclusion (or consequence).

Слайд 25


Conditional statements
Описание слайда:
Conditional statements

Слайд 26


Conditional statements The statement is called a conditional statement because asserts that is true on the condition that holds. A conditional statement is also called an implication.
Описание слайда:
Conditional statements The statement is called a conditional statement because asserts that is true on the condition that holds. A conditional statement is also called an implication.

Слайд 27


Conditional statements Because conditional statements play such an essential role in mathematical reasoning, a variety of terminology is used to express . You will encounter most if not all of the following ways to express this conditional statement: “if , then ” “ implies ” “ is sufficient for ” “a sufficient condition for is ” “ is necessary for ” “a necessary condition for is ” “ follows from ” “ unless ”
Описание слайда:
Conditional statements Because conditional statements play such an essential role in mathematical reasoning, a variety of terminology is used to express . You will encounter most if not all of the following ways to express this conditional statement: “if , then ” “ implies ” “ is sufficient for ” “a sufficient condition for is ” “ is necessary for ” “a necessary condition for is ” “ follows from ” “ unless ”

Слайд 28


Conditional statements Example 6 Let be the statement “Maria learns discrete mathematics” and the statement “Maria will find a good job.” Express the statement as a statement in English. Solution From the definition of conditional statements, we see that represents the statement “If Maria learns discrete mathematics, then she will find a good job.” There are many other ways to express this conditional statement in English. Among the most natural of these are: “Maria will find a good job when she learns discrete mathematics.” “For Maria to get a good job, it is sufficient for her to learn discrete mathematics.”
Описание слайда:
Conditional statements Example 6 Let be the statement “Maria learns discrete mathematics” and the statement “Maria will find a good job.” Express the statement as a statement in English. Solution From the definition of conditional statements, we see that represents the statement “If Maria learns discrete mathematics, then she will find a good job.” There are many other ways to express this conditional statement in English. Among the most natural of these are: “Maria will find a good job when she learns discrete mathematics.” “For Maria to get a good job, it is sufficient for her to learn discrete mathematics.”

Слайд 29


Converse, contrapositive and inverse We can form some new conditional statements starting with a conditional statement . In particular, there are three related conditional statements that occur so often that they have special names. The proposition is called the converse of . The contrapositive of is the proposition . The proposition is called the inverse of . We will see that of these three conditional statements formed from , only the contrapositive always has the same truth value as .
Описание слайда:
Converse, contrapositive and inverse We can form some new conditional statements starting with a conditional statement . In particular, there are three related conditional statements that occur so often that they have special names. The proposition is called the converse of . The contrapositive of is the proposition . The proposition is called the inverse of . We will see that of these three conditional statements formed from , only the contrapositive always has the same truth value as .

Слайд 30


Converse, contrapositive and inverse Example 7 What are the contrapositive, the converse, and the inverse of the conditional statement “The home team wins whenever it is raining?” Solution Because “ whenever ” is one of the ways to express the conditional statement , the original statement can be rewritten as “If it is raining, then the home team wins.” Consequently, the contrapositive of this conditional statement is “If the home team does not win, then it is not raining.” The converse is “If the home team wins, then it is raining.” The inverse is “If it is not raining, then the home team does not win.”
Описание слайда:
Converse, contrapositive and inverse Example 7 What are the contrapositive, the converse, and the inverse of the conditional statement “The home team wins whenever it is raining?” Solution Because “ whenever ” is one of the ways to express the conditional statement , the original statement can be rewritten as “If it is raining, then the home team wins.” Consequently, the contrapositive of this conditional statement is “If the home team does not win, then it is not raining.” The converse is “If the home team wins, then it is raining.” The inverse is “If it is not raining, then the home team does not win.”

Слайд 31


Biconditionals We now introduce another way to combine propositions that expresses that two propositions have the same truth value. Definition 7 Let and be propositions. The biconditional statement is the proposition “ if and only if .” The biconditional statement is true when and have the same truth values, and is false otherwise. Biconditional statements are also called bi-implications.
Описание слайда:
Biconditionals We now introduce another way to combine propositions that expresses that two propositions have the same truth value. Definition 7 Let and be propositions. The biconditional statement is the proposition “ if and only if .” The biconditional statement is true when and have the same truth values, and is false otherwise. Biconditional statements are also called bi-implications.

Слайд 32


Biconditionals
Описание слайда:
Biconditionals

Слайд 33


Biconditionals Note that the statement pq is true when both the conditional statements pq and qp are true and is false otherwise. That is why we use the words “if and only if” to express this logical connective and why it is symbolically written by combining the symbols and . There are some other common ways to express pq: “p is necessary and sufficient for q” “if p then q, and conversely” “p iff q” (The last way of expressing the biconditional statement pq uses the abbreviation “iff” for “if and only if”.)
Описание слайда:
Biconditionals Note that the statement pq is true when both the conditional statements pq and qp are true and is false otherwise. That is why we use the words “if and only if” to express this logical connective and why it is symbolically written by combining the symbols and . There are some other common ways to express pq: “p is necessary and sufficient for q” “if p then q, and conversely” “p iff q” (The last way of expressing the biconditional statement pq uses the abbreviation “iff” for “if and only if”.)

Слайд 34


Biconditionals Example 8 Let be the statement “You can take the flight,” and let be the statement “You buy a ticket.” Then is the statement “You can take the flight if and only if you buy a ticket.” This statement is true if and are either both true or both false, that is, if you buy a ticket and can take the flight or if you do not buy a ticket and you cannot take the flight. It is false when p and q have opposite truth values, that is, when you do not buy a ticket, but you can take the flight (such as when you get a free trip) and when you buy a ticket but you cannot take the flight (such as when the airline bumps you).
Описание слайда:
Biconditionals Example 8 Let be the statement “You can take the flight,” and let be the statement “You buy a ticket.” Then is the statement “You can take the flight if and only if you buy a ticket.” This statement is true if and are either both true or both false, that is, if you buy a ticket and can take the flight or if you do not buy a ticket and you cannot take the flight. It is false when p and q have opposite truth values, that is, when you do not buy a ticket, but you can take the flight (such as when you get a free trip) and when you buy a ticket but you cannot take the flight (such as when the airline bumps you).

Слайд 35


Truth tables of compound propositions We have now introduced four important logical connectives – conjunctions, disjunctions, conditional statements, and biconditional statements – as well as negations. We can use these connectives to build up complicated compound propositions involving any number of propositional variables.
Описание слайда:
Truth tables of compound propositions We have now introduced four important logical connectives – conjunctions, disjunctions, conditional statements, and biconditional statements – as well as negations. We can use these connectives to build up complicated compound propositions involving any number of propositional variables.

Слайд 36


Truth tables of compound propositions We can use truth tables to determine the truth values of these compound propositions. We use a separate column to find the truth value of each compound expression that occurs in the compound proposition as it is built up. The truth values of the compound proposition for each combination of truth values of the propositional variables in it is found in the final column of the table.
Описание слайда:
Truth tables of compound propositions We can use truth tables to determine the truth values of these compound propositions. We use a separate column to find the truth value of each compound expression that occurs in the compound proposition as it is built up. The truth values of the compound proposition for each combination of truth values of the propositional variables in it is found in the final column of the table.

Слайд 37


Truth tables of compound propositions Example 9 Construct the truth table of the compound proposition (pq)  (pq). Solution Because this truth table involves two propositional variables p and q, there are four rows in this truth table, one for each of the pairs of truth values TT, TF, FT, and FF.
Описание слайда:
Truth tables of compound propositions Example 9 Construct the truth table of the compound proposition (pq)  (pq). Solution Because this truth table involves two propositional variables p and q, there are four rows in this truth table, one for each of the pairs of truth values TT, TF, FT, and FF.

Слайд 38


Truth tables of compound propositions Example 9 Construct the truth table of the compound proposition (pq)  (pq). Solution The first two columns are used for the truth values of p and q, respectively. In the third column we find the truth value of q, needed to find the truth value of pq, found in the fourth column. The fifth column gives the truth value of pq. Finally, the truth value of (pq)  (pq) is found in the last column.
Описание слайда:
Truth tables of compound propositions Example 9 Construct the truth table of the compound proposition (pq)  (pq). Solution The first two columns are used for the truth values of p and q, respectively. In the third column we find the truth value of q, needed to find the truth value of pq, found in the fourth column. The fifth column gives the truth value of pq. Finally, the truth value of (pq)  (pq) is found in the last column.

Слайд 39


Truth tables of compound propositions Example 9 Construct the truth table of the compound proposition (pq)  (pq).
Описание слайда:
Truth tables of compound propositions Example 9 Construct the truth table of the compound proposition (pq)  (pq).

Слайд 40


Truth tables of compound propositions Example 9 Construct the truth table of the compound proposition (pq)  (pq).
Описание слайда:
Truth tables of compound propositions Example 9 Construct the truth table of the compound proposition (pq)  (pq).

Слайд 41


Truth tables of compound propositions Example 9 Construct the truth table of the compound proposition (pq)  (pq).
Описание слайда:
Truth tables of compound propositions Example 9 Construct the truth table of the compound proposition (pq)  (pq).

Слайд 42


Truth tables of compound propositions Example 9 Construct the truth table of the compound proposition (pq)  (pq).
Описание слайда:
Truth tables of compound propositions Example 9 Construct the truth table of the compound proposition (pq)  (pq).

Слайд 43


Truth tables of compound propositions Example 9 Construct the truth table of the compound proposition (pq)  (pq).
Описание слайда:
Truth tables of compound propositions Example 9 Construct the truth table of the compound proposition (pq)  (pq).

Слайд 44


Precedence of logical operators We can construct compound propositions using the negation operator and the logical operators defined so far. We will generally use parentheses to specify the order in which logical operators in a compound proposition are to be applied. For instance, ∨∧ is the conjunction of ∨ and .
Описание слайда:
Precedence of logical operators We can construct compound propositions using the negation operator and the logical operators defined so far. We will generally use parentheses to specify the order in which logical operators in a compound proposition are to be applied. For instance, ∨∧ is the conjunction of ∨ and .

Слайд 45


Precedence of logical operators This table displays the precedence levels of the logical operators, , ∧, ∨, , and .
Описание слайда:
Precedence of logical operators This table displays the precedence levels of the logical operators, , ∧, ∨, , and .

Слайд 46


Precedence of logical operators To reduce the number of parentheses, we specify that the negation operator is applied before all other logical operators. This means that p∧q is the conjunction of p and q, namely, (p)∧q, not the negation of the conjunction of p and q, namely (p∧q).
Описание слайда:
Precedence of logical operators To reduce the number of parentheses, we specify that the negation operator is applied before all other logical operators. This means that p∧q is the conjunction of p and q, namely, (p)∧q, not the negation of the conjunction of p and q, namely (p∧q).

Слайд 47


Precedence of logical operators Another general rule of precedence is that the conjunction operator takes precedence over the disjunction operator, so that p∧q∨r means (p∧q)∨r rather than p∧(q∨r).
Описание слайда:
Precedence of logical operators Another general rule of precedence is that the conjunction operator takes precedence over the disjunction operator, so that p∧q∨r means (p∧q)∨r rather than p∧(q∨r).

Слайд 48


Precedence of logical operators Finally, it is an accepted rule that the conditional and biconditional operators and have lower precedence than the conjunction and disjunction operators, ∧ and ∨. Consequently, p∨qr is the same as (p∨q)r. The conditional operator has precedence over the biconditional operator.
Описание слайда:
Precedence of logical operators Finally, it is an accepted rule that the conditional and biconditional operators and have lower precedence than the conjunction and disjunction operators, ∧ and ∨. Consequently, p∨qr is the same as (p∨q)r. The conditional operator has precedence over the biconditional operator.

Слайд 49


Tautologies and contradictions Definition 8 A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a tautology. A compound proposition that is always false is called a contradiction. A compound proposition that is neither a tautology nor a contradiction is called a contingency.
Описание слайда:
Tautologies and contradictions Definition 8 A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a tautology. A compound proposition that is always false is called a contradiction. A compound proposition that is neither a tautology nor a contradiction is called a contingency.

Слайд 50


Tautologies and contradictions Example 10 We can construct examples of tautologies and contradictions using just one propositional variable. Consider the truth tables of pp and pp.
Описание слайда:
Tautologies and contradictions Example 10 We can construct examples of tautologies and contradictions using just one propositional variable. Consider the truth tables of pp and pp.

Слайд 51


Tautologies and contradictions Example 10 Because p∨p is always true, it is a tautology. Because p∧p is always false, it is a contradiction.
Описание слайда:
Tautologies and contradictions Example 10 Because p∨p is always true, it is a tautology. Because p∧p is always false, it is a contradiction.

Слайд 52


Logical equivalences Definition 9 The compound propositions p and q are called logically equivalent if pq is a tautology. The notation pq denotes that p and q are logically equivalent. Remark: The symbol is not a logical connective, and pq is not a compound proposition but rather is the statement that pq is a tautology. The symbol is sometimes used instead of to denote logical equivalence.
Описание слайда:
Logical equivalences Definition 9 The compound propositions p and q are called logically equivalent if pq is a tautology. The notation pq denotes that p and q are logically equivalent. Remark: The symbol is not a logical connective, and pq is not a compound proposition but rather is the statement that pq is a tautology. The symbol is sometimes used instead of to denote logical equivalence.

Слайд 53


Logical equivalences One way to determine whether two compound propositions are equivalent is to use a truth table. In particular, the compound propositions p and q are equivalent if and only if the columns giving their truth values agree.
Описание слайда:
Logical equivalences One way to determine whether two compound propositions are equivalent is to use a truth table. In particular, the compound propositions p and q are equivalent if and only if the columns giving their truth values agree.

Слайд 54


Logical equivalences Example 11 Show that (pq) and pq are logically equivalent.
Описание слайда:
Logical equivalences Example 11 Show that (pq) and pq are logically equivalent.

Слайд 55


Logical equivalences Example 11 Show that (pq) and pq are logically equivalent.
Описание слайда:
Logical equivalences Example 11 Show that (pq) and pq are logically equivalent.

Слайд 56


Logical equivalences Example 11 Show that (pq) and pq are logically equivalent.
Описание слайда:
Logical equivalences Example 11 Show that (pq) and pq are logically equivalent.

Слайд 57


Logical equivalences Example 11 Show that (pq) and pq are logically equivalent.
Описание слайда:
Logical equivalences Example 11 Show that (pq) and pq are logically equivalent.

Слайд 58


Logical equivalences Example 11 Show that (pq) and pq are logically equivalent.
Описание слайда:
Logical equivalences Example 11 Show that (pq) and pq are logically equivalent.

Слайд 59


Logical equivalences Example 2 Show that (pq) and pq are logically equivalent.
Описание слайда:
Logical equivalences Example 2 Show that (pq) and pq are logically equivalent.

Слайд 60


Logical equivalences Example 11 Show that (pq) and pq are logically equivalent.
Описание слайда:
Logical equivalences Example 11 Show that (pq) and pq are logically equivalent.

Слайд 61


Logical equivalences
Описание слайда:
Logical equivalences

Слайд 62


Logical equivalences (pq)  pq This logical equivalence is one of the two De Morgan laws, named after the English mathematician Augustus De Morgan, of the mid-nineteenth century.
Описание слайда:
Logical equivalences (pq)  pq This logical equivalence is one of the two De Morgan laws, named after the English mathematician Augustus De Morgan, of the mid-nineteenth century.

Слайд 63


Logical equivalences Example 12 Show that pq and p∨q are logically equivalent. Solution: We construct the truth table for these compound propositions.
Описание слайда:
Logical equivalences Example 12 Show that pq and p∨q are logically equivalent. Solution: We construct the truth table for these compound propositions.

Слайд 64


Logical equivalences Example 12 Show that pq and p∨q are logically equivalent.
Описание слайда:
Logical equivalences Example 12 Show that pq and p∨q are logically equivalent.

Слайд 65


Logical equivalences Example 12 Show that pq and p∨q are logically equivalent.
Описание слайда:
Logical equivalences Example 12 Show that pq and p∨q are logically equivalent.

Слайд 66


Logical equivalences Example 12 Show that pq and p∨q are logically equivalent.
Описание слайда:
Logical equivalences Example 12 Show that pq and p∨q are logically equivalent.

Слайд 67


Logical equivalences Example 12 Show that pq and p∨q are logically equivalent.
Описание слайда:
Logical equivalences Example 12 Show that pq and p∨q are logically equivalent.

Слайд 68


Logical equivalences Example 12 Show that pq and p∨q are logically equivalent.
Описание слайда:
Logical equivalences Example 12 Show that pq and p∨q are logically equivalent.

Слайд 69


Logical equivalences Example 12 Show that pq and p∨q are logically equivalent. Because the truth values of p∨q and pq agree, they are logically equivalent.
Описание слайда:
Logical equivalences Example 12 Show that pq and p∨q are logically equivalent. Because the truth values of p∨q and pq agree, they are logically equivalent.

Слайд 70


Logical equivalences We will now establish a logical equivalence of two compound propositions involving three different propositional variables p, q, and r. To use a truth table to establish such a logical equivalence, we need eight rows, one for each possible combination of truth values of these three variables. We symbolically represent these combinations by listing the truth values of p, q, and r, respectively. These eight combinations of truth values are TTT, TTF, TFT, TFF, FTT, FTF, FFT, and FFF; we use this order when we display the rows of the truth table.
Описание слайда:
Logical equivalences We will now establish a logical equivalence of two compound propositions involving three different propositional variables p, q, and r. To use a truth table to establish such a logical equivalence, we need eight rows, one for each possible combination of truth values of these three variables. We symbolically represent these combinations by listing the truth values of p, q, and r, respectively. These eight combinations of truth values are TTT, TTF, TFT, TFF, FTT, FTF, FFT, and FFF; we use this order when we display the rows of the truth table.

Слайд 71


Logical equivalences Example 13 Show that p∨(q∧r) and (p∨q)∧(p∨r) are logically equivalent. This is the distributive law of disjunction over conjunction. Solution: We construct truth tables for these compound propositions. Because the truth values of p∨(q∧r) and (p∨q)∧(p∨r) agree, these compound propositions are logically equivalent.
Описание слайда:
Logical equivalences Example 13 Show that p∨(q∧r) and (p∨q)∧(p∨r) are logically equivalent. This is the distributive law of disjunction over conjunction. Solution: We construct truth tables for these compound propositions. Because the truth values of p∨(q∧r) and (p∨q)∧(p∨r) agree, these compound propositions are logically equivalent.

Слайд 72


A Demonstration That p(qr) and (pq)(pr) Are Logically Equivalent.
Описание слайда:
A Demonstration That p(qr) and (pq)(pr) Are Logically Equivalent.

Слайд 73


A Demonstration That p(qr) and (pq)(pr) Are Logically Equivalent.
Описание слайда:
A Demonstration That p(qr) and (pq)(pr) Are Logically Equivalent.

Слайд 74


A Demonstration That p(qr) and (pq)(pr) Are Logically Equivalent.
Описание слайда:
A Demonstration That p(qr) and (pq)(pr) Are Logically Equivalent.

Слайд 75


A Demonstration That p(qr) and (pq)(pr) Are Logically Equivalent.
Описание слайда:
A Demonstration That p(qr) and (pq)(pr) Are Logically Equivalent.

Слайд 76


A Demonstration That p(qr) and (pq)(pr) Are Logically Equivalent.
Описание слайда:
A Demonstration That p(qr) and (pq)(pr) Are Logically Equivalent.

Слайд 77


A Demonstration That p(qr) and (pq)(pr) Are Logically Equivalent.
Описание слайда:
A Demonstration That p(qr) and (pq)(pr) Are Logically Equivalent.

Слайд 78


A Demonstration That p(qr) and (pq)(pr) Are Logically Equivalent.
Описание слайда:
A Demonstration That p(qr) and (pq)(pr) Are Logically Equivalent.

Слайд 79


A Demonstration That p(qr) and (pq)(pr) Are Logically Equivalent.
Описание слайда:
A Demonstration That p(qr) and (pq)(pr) Are Logically Equivalent.

Слайд 80


Logical equivalences Next table contains some important equivalences. In these equivalences, T denotes the compound proposition that is always true and F denotes the compound proposition that is always false.
Описание слайда:
Logical equivalences Next table contains some important equivalences. In these equivalences, T denotes the compound proposition that is always true and F denotes the compound proposition that is always false.

Слайд 81


Propositional logic, слайд №81
Описание слайда:

Слайд 82


Propositional logic, слайд №82
Описание слайда:

Слайд 83


Logical equivalences Boolean algebra of propositions is a set P of all propositions with two binary operations: conjunction (∨) and disjunction (∧), logical constants T and F, and negation operator ( that satisfies the identity, complement, associative, commutative, and distributive laws.
Описание слайда:
Logical equivalences Boolean algebra of propositions is a set P of all propositions with two binary operations: conjunction (∨) and disjunction (∧), logical constants T and F, and negation operator ( that satisfies the identity, complement, associative, commutative, and distributive laws.

Слайд 84


Logical equivalences We also display some useful equivalences for compound propositions involving conditional statements and biconditional statements in Tables 2 and 3, respectively.
Описание слайда:
Logical equivalences We also display some useful equivalences for compound propositions involving conditional statements and biconditional statements in Tables 2 and 3, respectively.

Слайд 85


Propositional logic, слайд №85
Описание слайда:

Слайд 86


Propositional logic, слайд №86
Описание слайда:

Слайд 87


Using De Morgan’s Laws Example 13 Use De Morgan’s laws to express the negations of “Miguel has a cellphone and he has a laptop computer” and “Heather will go to the concert or Steve will go to the concert.” Solution: Let p be “Miguel has a cellphone” and q be “Miguel has a laptop computer.” Then “Miguel has a cellphone and he has a laptop computer” can be represented by p∧q. By the first of De Morgan’s laws,¬(p∧q) is equivalent to ¬p∨¬q. Consequently, we can express the negation of our original statement as “Miguel does not have a cellphone or he does not have a laptop computer.”
Описание слайда:
Using De Morgan’s Laws Example 13 Use De Morgan’s laws to express the negations of “Miguel has a cellphone and he has a laptop computer” and “Heather will go to the concert or Steve will go to the concert.” Solution: Let p be “Miguel has a cellphone” and q be “Miguel has a laptop computer.” Then “Miguel has a cellphone and he has a laptop computer” can be represented by p∧q. By the first of De Morgan’s laws,¬(p∧q) is equivalent to ¬p∨¬q. Consequently, we can express the negation of our original statement as “Miguel does not have a cellphone or he does not have a laptop computer.”

Слайд 88


Using De Morgan’s Laws Example 13 Use De Morgan’s laws to express the negations of “Miguel has a cellphone and he has a laptop computer” and “Heather will go to the concert or Steve will go to the concert.” Solution: Let r be “Heather will go to the concert” and s be “Steve will go to the concert.” Then “Heather will go to the concert or Steve will go to the concert” can be represented by r∨s. By the second of De Morgan’s laws, ¬(r∨s) is equivalent to ¬r∧¬s. Consequently, we can express the negation of our original statement as “Heather will not go to the concert and Steve will not go to the concert.”
Описание слайда:
Using De Morgan’s Laws Example 13 Use De Morgan’s laws to express the negations of “Miguel has a cellphone and he has a laptop computer” and “Heather will go to the concert or Steve will go to the concert.” Solution: Let r be “Heather will go to the concert” and s be “Steve will go to the concert.” Then “Heather will go to the concert or Steve will go to the concert” can be represented by r∨s. By the second of De Morgan’s laws, ¬(r∨s) is equivalent to ¬r∧¬s. Consequently, we can express the negation of our original statement as “Heather will not go to the concert and Steve will not go to the concert.”

Слайд 89


Constructing new logical equivalences The logical equivalences in Table 1, as well as any others that have been established (such as those shown in Tables 2 and 3), can be used to construct additional logical equivalences. The reason for this is that a proposition in a compound proposition can be replaced by a compound proposition that is logically equivalent to it without changing the truth value of the original compound proposition.
Описание слайда:
Constructing new logical equivalences The logical equivalences in Table 1, as well as any others that have been established (such as those shown in Tables 2 and 3), can be used to construct additional logical equivalences. The reason for this is that a proposition in a compound proposition can be replaced by a compound proposition that is logically equivalent to it without changing the truth value of the original compound proposition.

Слайд 90


Constructing new logical equivalences This technique is illustrated in Examples 14 – 16, where we also use the fact that if p and q are logically equivalent and q and r are logically equivalent, then p and r are logically equivalent.
Описание слайда:
Constructing new logical equivalences This technique is illustrated in Examples 14 – 16, where we also use the fact that if p and q are logically equivalent and q and r are logically equivalent, then p and r are logically equivalent.

Слайд 91


Constructing new logical equivalences Example 14 Show that (p  q) and p  q are logically equivalent. Solution: We will establish this equivalence by developing a series of logical equivalences, using one of the equivalences in Table 1 at a time, starting with (p  q) and ending with p  q .
Описание слайда:
Constructing new logical equivalences Example 14 Show that (p  q) and p  q are logically equivalent. Solution: We will establish this equivalence by developing a series of logical equivalences, using one of the equivalences in Table 1 at a time, starting with (p  q) and ending with p  q .

Слайд 92


Constructing new logical equivalences Example 14 Show that (p  q) and p  q are logically equivalent. Solution: We have the following equivalences. (p  q)  (p  q) – by Example 12  (p)  q – by the second De Morgan law  p  q – by the double negation law
Описание слайда:
Constructing new logical equivalences Example 14 Show that (p  q) and p  q are logically equivalent. Solution: We have the following equivalences. (p  q)  (p  q) – by Example 12  (p)  q – by the second De Morgan law  p  q – by the double negation law

Слайд 93


Constructing new logical equivalences Example 15 Show that (p  (p  q)) and (p  q) are logically equivalent by developing a series of logical equivalences. Solution: We will use one of the equivalences in Table 1 at a time, starting with (p  (p  q)) and ending with (p  q) . (Note: we could also easily establish this equivalence using a truth table.)
Описание слайда:
Constructing new logical equivalences Example 15 Show that (p  (p  q)) and (p  q) are logically equivalent by developing a series of logical equivalences. Solution: We will use one of the equivalences in Table 1 at a time, starting with (p  (p  q)) and ending with (p  q) . (Note: we could also easily establish this equivalence using a truth table.)

Слайд 94


Constructing new logical equivalences Example 15 Show that (p  (p  q)) and (p  q) are logically equivalent by developing a series of logical equivalences. Solution: We have the following equivalences. (p  (p  q))  p  (p  q)  p  ((p)  q)  p  (p  q)  (p  p)  (p  q)  F  (p  q)  (p  q)  F  (p  q)
Описание слайда:
Constructing new logical equivalences Example 15 Show that (p  (p  q)) and (p  q) are logically equivalent by developing a series of logical equivalences. Solution: We have the following equivalences. (p  (p  q))  p  (p  q)  p  ((p)  q)  p  (p  q)  (p  p)  (p  q)  F  (p  q)  (p  q)  F  (p  q)

Слайд 95


Constructing new logical equivalences Example 16 Show that (p  q)  (p  q) is a tautology. Solution: (p  q)  (p  q)   (p  q)  (p  q)  (p  q)  (p  q)  (p  p)  (q  q)  T  T  T
Описание слайда:
Constructing new logical equivalences Example 16 Show that (p  q)  (p  q) is a tautology. Solution: (p  q)  (p  q)   (p  q)  (p  q)  (p  q)  (p  q)  (p  p)  (q  q)  T  T  T

Слайд 96


Propositional satisfiability Definition 10 A compound proposition is satisfiable if there is an assignment of truth values to its variables that makes it true. When no such assignments exists, that is, when the compound proposition is false for all assignments of truth values to its variables, the compound proposition is unsatisfiable. Note that a compound proposition is unsatisfiable if and only if its negation is true for all assignments of truth values to the variables, that is, if and only if its negation is a tautology.
Описание слайда:
Propositional satisfiability Definition 10 A compound proposition is satisfiable if there is an assignment of truth values to its variables that makes it true. When no such assignments exists, that is, when the compound proposition is false for all assignments of truth values to its variables, the compound proposition is unsatisfiable. Note that a compound proposition is unsatisfiable if and only if its negation is true for all assignments of truth values to the variables, that is, if and only if its negation is a tautology.

Слайд 97


Propositional satisfiability Definition 11 When we find a particular assignment of truth values that makes a compound proposition true, we have shown that it is satisfiable; such an assignment is called a solution of this particular satisfiability problem.
Описание слайда:
Propositional satisfiability Definition 11 When we find a particular assignment of truth values that makes a compound proposition true, we have shown that it is satisfiable; such an assignment is called a solution of this particular satisfiability problem.

Слайд 98


Propositional satisfiability However, to show that a compound proposition is unsatisfiable, we need to show that every assignment of truth values to its variables makes it false. Although we can always use a truth table to determine whether a compound proposition is satisfiable, it is often more efficient not to, as Example 17 demonstrates.
Описание слайда:
Propositional satisfiability However, to show that a compound proposition is unsatisfiable, we need to show that every assignment of truth values to its variables makes it false. Although we can always use a truth table to determine whether a compound proposition is satisfiable, it is often more efficient not to, as Example 17 demonstrates.

Слайд 99


Propositional satisfiability Example 17 Determine whether each of the compound propositions (p  q)  (q  r)  (r  p) , (p  q  r)  (p  q  r) , (p  q)  (q  r)  (r  p)  (p  q  r)  (p  q  r) is satisfiable.
Описание слайда:
Propositional satisfiability Example 17 Determine whether each of the compound propositions (p  q)  (q  r)  (r  p) , (p  q  r)  (p  q  r) , (p  q)  (q  r)  (r  p)  (p  q  r)  (p  q  r) is satisfiable.

Слайд 100


Propositional satisfiability Example 17 Solution: (p  q)  (q  r)  (r  p) is satisfiable (p T, q T, r T); (p  q  r)  (p  q  r) is satisfiable (p T, q F, r T); (p  q)  (q  r)  (r  p)  (p  q  r)  (p  q  r) is unsatisfiable (why?).
Описание слайда:
Propositional satisfiability Example 17 Solution: (p  q)  (q  r)  (r  p) is satisfiable (p T, q T, r T); (p  q  r)  (p  q  r) is satisfiable (p T, q F, r T); (p  q)  (q  r)  (r  p)  (p  q  r)  (p  q  r) is unsatisfiable (why?).

Слайд 101


Satisfiability problem Many problems, in diverse areas such as robotics, software testing, computer-aided design, machine vision, integrated circuit design, computer networking, genetics, can be modeled in terms of propositional satisfiability. In particular, we will show how to use propositional satisfiability to model Sudoku puzzles.
Описание слайда:
Satisfiability problem Many problems, in diverse areas such as robotics, software testing, computer-aided design, machine vision, integrated circuit design, computer networking, genetics, can be modeled in terms of propositional satisfiability. In particular, we will show how to use propositional satisfiability to model Sudoku puzzles.

Слайд 102


Sudoku 99 A Sudoku puzzle is represented by a 9×9 grid made up of nine 3×3 subgrids, known as blocks. For each puzzle, some of the 81 cells, called givens, are assigned one of the numbers 1,2,...,9, and the other cells are blank.
Описание слайда:
Sudoku 99 A Sudoku puzzle is represented by a 9×9 grid made up of nine 3×3 subgrids, known as blocks. For each puzzle, some of the 81 cells, called givens, are assigned one of the numbers 1,2,...,9, and the other cells are blank.

Слайд 103


Sudoku 99 The puzzle is solved by assigning a number to each blank cell so that every row, every column, and every one of the nine 3×3 blocks contains each of the nine possible numbers.
Описание слайда:
Sudoku 99 The puzzle is solved by assigning a number to each blank cell so that every row, every column, and every one of the nine 3×3 blocks contains each of the nine possible numbers.

Слайд 104


Sudoku 99 Exercise Construct a compound proposition that asserts that every cell of a 9×9 Sudoku puzzle contains at least one number.
Описание слайда:
Sudoku 99 Exercise Construct a compound proposition that asserts that every cell of a 9×9 Sudoku puzzle contains at least one number.

Скачать

Теги Propositional logic
Похожие презентации
Mypresentation.ru
Загрузить презентацию