Logic

1.1 Propositions and logical operations

Logic is the study of formal reasoning. Proposition: statement that is either true or false.

• declarative statements can be true or false so they can be prepositions, but questions and commands are not,
• A compound proposition connects individual proposition with logical operators.

Logical connectives are operators used to create compound propositions from other propositions

• Negation: NOT, $\lnot$,
• Conjunction: AND $\land$
• Disjunction: inclusive OR, $\lor$, exclusive OR, $\oplus$
• Implication: IF-THEN, $\rightarrow$
• Biconditional: IF-AND-ONLY-IF, $\leftrightarrow$

Truth tables: define meanings for logical connectives. It has one row for each combination of truth values for propositions in a statement using the connective.

• $2^n$ rows where $n$ is the number of propositions.
• good for checking equivalence

Implications: $P$ (antecedent) implies $Q$ (consequent), or $P \rightarrow Q$, means if $P$ then $Q$.

• an implication is always true in cases where the antecedent is false.
• Different phrasings for $P \rightarrow Q$
  • If $P$ then $Q$
  • $P$ implies $Q$
  • $Q$ only if $P$

1.2 Evaluating compound operations

The order of evaluation is negation, conjunction, then disjunction

When filling in the truth table, the right most column should have a TFTF... pattern.

1.3 Conditional statements

The conditional operation is denoted with $\rightarrow$. In $p \rightarrow q$, the proposition $p$ is called the hypothesis and q is the conclusion.

The converse of $p \rightarrow q$ is $q \rightarrow p$. The contrapositive of $p \rightarrow q$ is $\lnot q \rightarrow \lnot p$ The inverse of $p \rightarrow q$ is $\lnot p \rightarrow \lnot q$

1.4 Logical Equivalence

A compound proposition is a tautology if the proposition is always true, regardless of the truth value of the individual propositions that occur in it. It's a contradiction if the proposition is always false.

• prove with truth table

Truth table can also prove that two compound propositions are logically equivalent. Two compound propositions are logically equivalent if

De Morgan's laws are logical equivalences that show how to correctly distribute a negation operation inside a parenthesized expression.

The first law is: $\lnot (p \lor q) \equiv (\lnot p \land \lnot q)$ The second law swaps the role of the disjunctino and conjunction: $\lnot(p \land q ) \equiv (\lnot p \lor \lnot q)$

1.5 Laws of propositional logic

if two propositions are logically equivalent, then they can be substituted.

1.6 Logical reasoning

Logic allows us to formally establish the truth of logical statements, assuming that a set of hypotheses is true. An argument is a set of propositions, each called hypotheses, followed by a final proposition called a conclusion. Whenever the hypotheses of an argument are all true, the conclusion is valid if true, invalid otherwise.

To access the validity of an argument, use a truth table. Create one for all the hypotheses and the conclusion. If there are any row in which all hypotheses are true but the conclusion is false, then the argument is invalid.

1.7 Rules of inference with propositions

Some arguments can be shown to be valid by applying rules that are arguments already shown to be valid.

Establishing the validity of an argument by applying the rules of inference and laws of propositional logic is a logical proof, which is a sequence of steps, each consisting of a proposition and justification.

Laws of propositional logic establish that certain pairs of propositions are logically equivalent. Therefore, the direction goes both way. By contrast, proofs of logical arguments have a well defined direction.

1.8 Predicate and Quantifiers

A predicate is a logical statement whose truth function is of one or more variables.

• If it doesn't have a variable, then it is a proposition
• to turn a predicate into a proposition to use a quantifier The domain of a variable in a predicate is the set of all possible values for the variable.

If all the variables in a predicate are assigned specific values, then the predicate becomes a proposition with a well defined truth value. A quantifier does this.

• the symbol $\forall$ is the universal quantifier and $\forall x P(x)$ asserts that $P(x)$ is true for every possible value of $x$ in its domain and its called the universally quantified statement.
  • $\forall x P(x) \equiv P(a_1) \land P(a_2) \land ... \land P(a_k)$ if the domain is a finite set of elements $\{a_1, a_2, ..., a_k\}$. The equivalence symbol means that the two expressions always has the same truth value regardless of the truth values of $P(a_1), ..., P(a_n)$

A counterexample for a universally quantified statement is an element in the domain for which the predicate is false. A

An existential quantifier is the symbol $\exists$. The statement $\exists x P(x)$ asserts that $P(x)$ is true for at least one possible value for $x$ in its domain. The entire statement is called an existentially quantified statement.

• an example for an existentially quantified statement is an element in the domain for which the predicate is true, and one is sufficient to show that an existentially quantified statement is true.
• to show that the statement is false, you must prove statement is always false.

1.9 Quantified Statements

Universal and existential quantifiers are generally called quantifiers, and a logical statement that includes a quantifier is called a quantified statement.

• Apply the quantifiers before the logical operations used for propositions. This means that $\forall x P(x) \land Q(x)$ is equivalent to $(\forall x P(x)) \land Q(x)$

A variable $x$ in the predicate $P(x)$ is called a free variable because the variable is free to take on any value in the domain. The variable $x$ in the statement $\forall x P(x)$ is a bound variable because the variable is bound to a quantifier. A statement with no free variables is a proposition because the statement's truth value can be determined.

Two quantified statements have the same logical meaning if they have the same truth value regardless of value of the predicates for the elements in the domain.

1.10 De Morgan's law for quantified statements

The negation operation can be applied to a quantified statement.

• "not every bird can fly" is logically equivalent to "there exists a bird that cannot fly"

De Morgan's law for universally quantified statements: $\lnot \forall x P(x) \equiv \exists x \lnot P(x)$ Thus, $\lnot P(a_1) \land P(a_2) ... \equiv \lnot P(a_1) \lor \lnot P(a_2) ...$

De Morgan's law for existentially quantified statements/ $\lnot \exists x P(x) \equiv \forall x \lnot P(x)$

1.11 Nested Quantifiers

A logical expression with more than one quantifier that binds different variables in the same predicate is said have nested quantifiers.

$\forall x \exists y P(x,y)$ means that both $x$ and $y$ are bound.

The order of the quantifiers matters. Quantifiers are applied from left to right.

• Think of it like a two player game in which existential player tries to make the expression true and the universal player tries to make the expression false.

De Morgan's law also applies here:

• $\lnot \forall x \forall y P(x,y) = \exists x \exists y \lnot P(x,y)$
• $\lnot \forall x \exists y P(x,y) = \exists x \forall y \lnot P(x,y)$
• $\lnot \exists x \forall y P(x,y) = \forall x \exists y \lnot P(x,y)$
• $\lnot \exists x \exists y P(x,y) = \forall x \forall y \lnot P(x,y)$

Each time, the negation sign moves past a quantifier and the type changes.

1.12 More Nested Quantified Statements

"someone else" in logic would be expressed as $\forall x \forall y ((x \neq y) \rightarrow M(x,y))$

• where $M(x,y)$ indicates that $x$ sent the email to $y$.

to express uniqueness, you need to add that everything else is false. $\exists x (L(x) \land \forall y ((x\neq y) \rightarrow \lnot L(y))$

• where $L(x)$: $x$ was late to the meeting.

1.13 Rules of inference with quantifiers

To apply rules of inference to quantified expressions, you must remove the quantifier by plugging in a value from the domain to replace variable $x$, or an element of the domain of $x$.

• the value can be an arbitrary element of a domain and give it a generic name. E.g., $c$. A particular element is one that has properties that are not shared by all elements of the domain. E.g., $3$.

If the element is defined in a hypothesis, it is always a particular element and the definition fo that element in the proof is labeled "hypothesis". If an element is introduced for the first time in the proof, the definition is labeled "element definition" and you must define whether the element is arbitrary or particular.

Existential/universal instantiation replaces a quantified variable with an element of the domain.

• each use of existential instantiation must define a new element with its own name.
• universal instantiation can be used with a particular or arbitrary element. Existential/universal generalization replace an element of the domainw ith quantified variable
• both only applies to non-nested quantifiers.
• universal generalization can only be applied if the element is arbitrary

Make sure you define a new particular element with a new name for each use of existential instantiation within the same logical proof to avoid a faulty proof that an invalid argument is valid.