COSC50 Discrete Structures 1

Lesson 1 and 2

Logical Argument

The science that evaluates arguments, plays a central role in mathematics, and is essential for constructing and testing computer programs.

Proposition

A declarative sentence that is either true or false.

Statement

A sentence that is either true or false, typically declarative. Example: “World War II began in 1939.”

Truth-Value

The attribute by which a statement is either true or false.

Argument

A group of statements, where the conclusion is claimed to follow from the premises.

Premise

A statement or proposition in an argument that provides support or evidence for the conclusion.

Conclusion

The statement in an argument that the premises support; the point the argument is trying to make.

Inference

The rational movement from premises to conclusion; a conclusion drawn on the basis of reasons.

Good Argument

An argument in which the conclusion really does follow from the premises.

Bad Argument

An argument in which the conclusion does not follow from the premises, even though it is claimed to.

Non-Statement

Questions, proposals, suggestions, commands, and exclamations that cannot be classified as true or false.

Example of Good Argument

“All cats are animals. Garfield is a cat. Therefore, Garfield is an animal.”

Example of Bad Argument

“Some dogs are aspin. Scooby Doo is a dog. Therefore, Scooby Doo is an aspin.”

Propositional Variable

A variable (p, q, r, etc.) used to represent propositions. Plays the same role as numerical variables in arithmetic.

Atomic Proposition

A single propositional variable or a single propositional constant (True or False). Example: P = “A computer is an animal.”

Compound Proposition

A proposition containing at least one logical connective. Example: P ∧ Q.

Negation (¬P or –P)

The opposite of a proposition. True if P is false, false if P is true.

Conjunction (P ∧ Q)

True only if both P and Q are true. Expressed with “and”.

Disjunction (P ∨ Q)

False only if both P and Q are false; otherwise true. Expressed with “or”.

Conditional / Implication (P ⇒ Q)

False only if P is true and Q is false; otherwise true. Expressed as “If P, then Q”.

Biconditional / Equivalence (P ⇔ Q)

True if P and Q have the same truth values, otherwise false. Expressed as “P if and only if Q”.

Negation (¬P)

• If P = T, then ¬P = F

• If P = F, then ¬P = T

Conjunction (P ∧ Q)

Only true when both P and Q are true

Disjunction (P ∨ Q)

Only false when both P and Q are false

Conditional (P ⇒ Q)

Only false when P = T and Q = F

Biconditional (P ⇔ Q)

True when P and Q have the same truth value

Logical Connective

A symbol or word that connects propositions to form compound propositions (for example negation, conjunction, disjunction, implication, and biconditional).

Propositional Variable (introduced by Aristotle)

A symbol (commonly p, q, r) that represents a proposition. Aristotle first introduced using symbolic variables to stand for statements. Propositional variables let us make general forms of logical expressions.

Example of True Statements

“World War II began in 1939.”
“2 + 2 = 4.”
“Water freezes at 0°C (at standard atmospheric pressure).”
“Cats are mammals.”

Example of False Statements

“Some cats are dogs.”
“The sun rises in the west.”
“2 + 2 = 5.”
“Water boils at 50°C at sea level.”