Logic Flashcards

1
Q

What is a proposition?

A

A proposition is a declarative sentence that is either true or false, but not both.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is a compound proposition?

A

Many mathematical statements are constructed by combining one or more existing propositions; new propositions, called compound propositions, are formed from existing propositions using logical operators.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What will the truth table look like if p and q are in conjunction?

A

TFFF. 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 ∧ operator for the two propositions p and q can also be understood as min(p,q) where true is represented with 1 and false is represented with 0.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What will the truth table look like if p and q are in disconjunction?

A

TTTF. 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 ∨ operator for the two propositions p and q can also be understood as max(p, q) where true is represented with 1 and false is represented with 0.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What will the truth table look like if p and q are in an or-statement (the proposition that is true when exactly one of p and q is true and is false otherwise)?

A

FTTF. 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 ⊕ operator for the two propositions p and q can also be understood as sum(p, q) == 1 where true is represented with 1 and false is represented with 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What will the truth table look like if p and q are in a conditional statement?

A

TFTT. The conditional statement p =⇒ q is the proposition “if p, then q.” The conditional statement p =⇒ q is false when p is true and q is false, and true otherwise. In the conditional statement p =⇒ q, p is called the hypothesis (or antecedent or premise), and q is called the conclusion (or consequence). The =⇒ operator for the two propositions p and q can also be understood as max(¬(p),q) where true is represented with 1 and false is represented with 0. The statement p =⇒ q is called a conditional statement because p =⇒ q asserts that q is true on the condition that p holds. A conditional statement is also called an implication. The truth table for the conditional statement p =⇒ q is shown in table above. Note that the statement p =⇒ q is true when both p and q are true and when p is false (no matter what the truth value of q is).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What will the truth table look like if p and q are in a biconditional statement?

A

TFFT. The biconditional statement p ⇐⇒ q is the proposition “p if and only if q.” The biconditional statement p ⇐⇒ q is true when p and q have the same truth values, and is false otherwise. Biconditional statements are also called bi-implications. The ⇐⇒ operator for the two propositions p and q can also be understood as |(p − q)| == 0 where true is represented with 1 and false is represented with 0.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is a tautology?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a compound proposition that is always false called?

A

A contradiction.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is a contingency?

A

A compound proposition that is neither a tautology nor a contradiction is called a contingency.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

When is a compound proposition considered logically equivalent?

A

The compound propositions p and q are called logically equivalent if p ⇐⇒ q is a tautology. The notation p ≡ q denotes that p and q are logically equivalent.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Why are the two logical equivalences known as De Morgan’s laws are particularly important?

A

They tell us how to negate conjunctions and how to negate disjunctions. In particular, the equivalence ¬(p ∨ q) ≡ ¬p ∧ ¬q tells us that the negation of a disjunction is formed by taking the conjunction of the negations of the component propositions. Similarly, the equivalence ¬(p ∧ q) ≡ ¬p ∨ ¬q tells us that the negation of a conjunction is formed by taking the disjunction of the negations of the component propositions.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Use De Morgan’s laws to express the negations of “Miguel has a cellphone and he has a laptop computer”

A

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. Because of the first of De Morgan’s laws, we can express the negation of our original statement as
“Miguel does not have a cellphone or he does not have a laptop computer.”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Use De Morgan’s laws to express the negations of “Heather will go to the concert or Steve will go to the concert.”

A

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. Because of the second of De Morgans laws, 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.”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

When is a compound proposition satisfiable?

A

A compound proposition satisfiable if there is an assignment of truth values to its variables that makes it true.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

When is a compound proposition unsatisfiable?

A

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, i.e., if and only if its negation is a tautology.

17
Q

What does quantifiers express?

A

Quantification expresses the extent, to which a predicate is true over a range of elements. In English, the words all, some, many, none, and few are used in quantifications

18
Q

How is a universal quantification expressed?

A

he universal quantification of P(x) is the statement

“P(x) for all values of x in the domain.”

19
Q

How is a existential quantification expressed?

A

“There exists an element x in the domain such that P(x) evaluates to true.”

20
Q

What do the Identity laws say?

A

p ∧ T ≡ p

p ∨ F≡ p

21
Q

What do the Domination laws say?

A

p ∨ T ≡ T

p ∧ F ≡ F

22
Q

What do the Idempotent laws say?

A

p ∨ p ≡ p

p ∧ p ≡ p

23
Q

What do the Double negations laws say?

A

¬(¬p) ≡ p

24
Q

What do the Commutative laws say?

A

p ∨ q ≡ q ∨ p

p ∧ q ≡ q ∧ p

25
Q

What do the Associative laws say?

A

(p∨q)∨r ≡p∨(q∨r)

p∧q)∧r ≡p∧(q∧r

26
Q

What do the Distributive laws say?

A

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

27
Q

What do the De Morgan’s laws say?

A

¬(p ∧ q) ≡ ¬p ∨ ¬q

¬(p ∨ q) ≡ ¬p ∧ ¬q

28
Q

What do the Absorption laws say?

A

p ∨ (p ∧ q) ≡ p

p ∧ (p ∨ q) ≡ p

29
Q

What do the Negation laws say?

A

p ∨ ¬p ≡ T

p ∧ ¬p ≡ F

30
Q

The proposition q =⇒ p is called the ….. of p =⇒ q.

A

Converse

31
Q

The …… of p =⇒ q is the proposition ¬q =⇒ ¬p.

A

Contrapositive

32
Q

The proposition ¬p =⇒ ¬q is called the ….. of p =⇒ q.

A

Inverse

33
Q

A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a …..

A

Tautology

34
Q

A compound proposition that is neither a tautology nor a contradiction is called a ….

A

Contingency

35
Q

Explain, without using a truth table, why (p ∨ q ∨ r) ∧ (¬p ∨ ¬q ∨ ¬r) is true when at least one of p, q, and r is true and at least one is false, but is false when all three variables have the same truth value.

A

The first clause is true if and only if at least one of p, q, and r is true. The second clause is true if and only if at least one of the three variables is false. Therefore the entire statement is true if and only if there is at least one T and one F among the truth values of the variables, in other words, that they don’t all have the same truth value.