Q. Translate the statement “The sum of two positive integers is always positive” into a logical expression.
We first rewrite it so that the implied quantifiers and a domain are shown:
For every two integers, if these integers are both positive, then the sum of these integers is positive.
We introduce the variables x and y to obtain “For all positive integers x and y, x + y is positive.
∀x∀y((x > 0) ∧ (y > 0) → (x + y > 0))
where the domain for both variables consists of all integers.
Q. Translate the statement “Every real number except zero has a multiplicative inverse.” (A multiplicative inverse of a real number x is a real number y such that xy = 1).
We first rewrite this as “For every real number x except zero, x has a multiplicative inverse.”
We can rewrite this as “For every real number x, if x ≠ 0, then there exists a real number y such that xy = 1.” This can be rewritten as
∀x((x ≠ 0) → ∃y(xy = 1)).
Q. Translate the statement ∀x(C(x) ∨ ∃y(C(y) ∧ F(x,y))) into English, where C(x) is “x has a computer,” F(x,y) is “x and y are friends,” and the domain for both x and y consists of all students in your school.
The statement says that for every student x in your school, x has a computer or there is a student y such that y has a computer and x and y are friends. In other words, every student in your school has a computer or has a friend who has a computer.
Translate the statement ∃x∀y∀z((F (x, y) ∧ F(x,z)∧ (y ≠ z)) → ¬F(y,z)) into English, where F(a,b)means a and b are friends and the domain for x, y, and z consists of all students in your school.
This expression says that if students x and y are friends, and students x and z are friends, and furthermore, if y and z are not the same student, then y and z are not friends.
It follows that the original statement, which is triply quantified, says that there is a student x such that for all students y and all students z other than y, if x and y are friends and x and z are friends, then y and z are not friends.
In other words, there is a student none of whose friends are also friends with each other.
Express the statement “If a person is female and is a parent, then this person is someone’s mother” as a logical expression involving predicates, quantifiers with a domain consisting of all people, and logical connectives.
The statement “If a person is female and is a parent, then this person is someone’s mother” can be expressed as “For every person x, if person x is female and person x is a parent, then there exists a person y such that person x is the mother of person y.”
We introduce the propositional functions F(x) to represent “x is female,” P(x) to represent “x is a parent,” and M(x, y) to represent “x is the mother of y.” The original statement can be represented as
∀x((F (x) ∧ P(x)) → ∃yM(x, y)).
Q. Express the statement “Everyone has exactly one best friend” as a logical expression involving predicates, quantifiers with a domain consisting of all people, and logical connectives.
The statement “Everyone has exactly one best friend” can be expressed as “For every person x, person x has exactly one best friend.” Introducing the universal quantifier, we see that this statement is the same as “∀x(person x has exactly one best friend),” where the domain consists of all people.
To say that x has exactly one best friend means that there is a person y who is the best friend of x, and furthermore, that for every person z, if person z is not person y, then z is not the best friend of x.
When we introduce the predicate B(x, y) to be the statement “y is the best friend of x,” the statement that x has exactly one best friend can be represented as
∃y(B(x, y) ∧ ∀z((z ≠ y) → ¬B(x, z))).
Use quantifiers to express the statement “There is a woman who has taken a flight on every airline in the world.”
Let P(w,f) be “w has taken f ” and Q(f, a) be “f is a flight on a.” We can express the statement as ∃w∀a∃f(P(w,f) ∧ Q(f,a))
where the domains of discourse for w,f, and a consist of all the women in the world, all airplane flights, and all airlines, respectively.
Proofs in mathematics are valid arguments that establish the truth of mathematical statements.
By an argument, we mean a sequence of statements that end with a conclusion. By valid, we mean that the conclusion, or final statement of the argument, must follow from the truth of the preceding statements, or premises, of the argument.
Consider the following argument involving propositions (which, by definition, is a sequence of propositions):
“If you have a current password, then you can log onto the network.”
“You have a current password.”
Therefore, “You can log onto the network.”
Determine whether this is a valid argument.
Before we discuss the validity of this particular argument, we will look at its form. Use p to represent “You have a current password” and q to represent “You can log onto the network.” Then, the argument has the form
p → q p ------- ∴q
where ∴ is the symbol that denotes “therefore.”
We say this form of argument is valid because whenever all its premises (all statements in the argument other than the final one, the conclusion) are true, the conclusion must also be true.
Using this notation, the hypotheses are written in a column, followed by a horizontal bar, followed by a line that begins with the therefore symbol and ends with the conclusion.
Definitions :
An argument in propositional logic is a sequence of propositions.
All but the final proposition in the argument are called premises and the final proposition is called the conclusion.
An argument is valid if the truth of all its premises implies that the conclusion is true.
Rule of Inference - Modus ponens
p p → q ------ ∴ q
The tautology (p ∧ (p → q)) → q
Rule of Inference - Hypothetical syllogism
p → q q → r ------- ∴ p → r
The tautology (p → q) ∧ (q → r)) → (p → r)
Example :State which rule of inference is used in the argument: If it rains today, then we will not have a barbecue today. If we do not have a barbecue today, then we will have a barbecue tomorrow. Therefore, if it rains today, then we will have a barbecue tomorrow.
Let p be the proposition “It is raining today,” let q be the proposition “We will not have a barbecue today,” and let r be the proposition “We will have a barbecue tomorrow.” Then this argument is of the form
p → q q → r ----- ∴ p → r
Hence, this argument is a hypothetical syllogism.
Rule of Inference - Modus tollens
¬q p → q ------ ∴ ¬p
Tautology : (¬q ∧ (p → q)) → ¬p
This tells us that if a conditional statement "q" is false and the hypothesis of this conditional statement "p → q" is true, then the conclusion must be false"q"
Rule of Inference - Disjunctive syllogism
p ∨ q ¬p ------ ∴ q
The tautology ((p ∨ q) ∧ ¬p) → q
Rule of Inference - Addition
p ----- ∴ p ∨ q
The tautology p → (p ∨ q)
Example :State which rule of inference is the basis of the following argument: “It is below freezing now. Therefore, it is either below freezing or raining now.”
Let p be the proposition “It is below freezing now” and q the proposition “It is raining now.” Then this argument is of the form
p ------ ∴ p ∨ q
This is an argument that uses the addition rule.
Rule of Inference - Simplification
p ∧ q ----- ∴ p
The tautology (p ∧ q) → p
Example :State which rule of inference is the basis of the following argument: “It is below freezing and raining now. Therefore, it is below freezing now.
Let p be the proposition “It is below freezing now,” and let q be the proposition “It is raining now.” This argument is of the form
p ∧ q ------ ∴ p
This argument uses the simplification rule.
Rule of Inference - Conjunction
p q ----- ∴ p ∧ q
The tautology ((p) ∧ (q)) → (p ∧ q)
Rule of Inference - Resolution
p ∨ q ¬p ∨ r ------ ∴ q ∨ r
The tautology ((p ∨ q) ∧ (¬p ∨ r)) → (q ∨ r)
Example : Use resolution to show that the hypotheses “Jasmine is skiing or it is not snowing” and “It is snowing or Bart is playing hockey” imply that “Jasmine is skiing or Bart is playing hockey.”
Let p be the proposition “It is snowing,” q the proposition “Jasmine is skiing,” and r the proposition “Bart is playing hockey.”
We can represent the hypotheses as ¬p ∨ q and p ∨ r, respectively.
Using resolution, the proposition q ∨ r, “Jasmine is skiing or Bart is playing hockey,” follows.
Example : Show that the premises (p ∧ q) ∨ r and r → s imply the conclusion p ∨ s.
We can rewrite the premises (p ∧ q) ∨ r as two clauses, p ∨ r and q ∨ r. We can also replace r → s by the equivalent clause ¬r ∨ s.
Using the two clauses p ∨ r and ¬r ∨ s, we can use resolution to conclude p ∨ s.
Fallacy of affirming the conclusion
The proposition ((p → q) ∧ q) → p is not a tautology, because it is false when p is false and q is true.
However, the argument with premises p → q and q and conclusion p as a valid argument form although it is not.
This type of incorrect reasoning is called the fallacy of affirming the conclusion.
Example Is the following argument valid? If you do every problem in a book, then you will learn discrete mathematics. You learned discrete mathematics. Therefore, you did every problem in this book.
Let p be the proposition “You did every problem in this book.” Let q be the proposition “You learned discrete mathematics.” Then this argument is of the form: if p → q and q, then p.
It is possible for you to learn discrete mathematics in some way other than by doing every problem in that book.
This is an example of an incorrect argument using the fallacy of affirming the conclusion.
Fallacy of denying the hypothesis
The proposition ((p → q) ∧ ¬p) → ¬q is not a tautology, because it is false when p is false and q is true.
Many incorrect arguments use this incorrectly as a rule of inference. This type of incorrect reasoning is called the fallacy of denying the hypothesis
Q. If the conditional statement p → q is true, and ¬p is true, is it correct to conclude that ¬q is true? In other words, is it correct to assume that you did not learn discrete mathematics if you did not do every problem in the book, assuming that if you do every problem in this book, then you will learn discrete mathematics?
It is possible that you learned discrete mathematics even if you did not do every problem in this book. This incorrect argument is of the form p → q and ¬p imply ¬q, which is an example of the fallacy of denying the hypothesis