Unit 1: Logic and Proofs - Subjective Questions

Proposition: A proposition is a declarative sentence that has exactly one truth value: either true or false.

• Example: is a true proposition.
• Example: is a false proposition.
• Questions, commands, and open sentences such as are not propositions unless the variable is assigned a value or quantified.

Simple proposition: A proposition that does not contain another proposition as a component.

• Example: : "The server is running."

Compound proposition: A proposition formed by combining one or more propositions using logical connectives.

• Negation:
• Conjunction:
• Disjunction:
• Implication:
• Biconditional:

For example, if means "It is raining" and means "The road is wet," then means "If it is raining, then the road is wet."

The truth table is:

The final column is true in every row. Therefore, the biconditional is a tautology, and the two expressions are logically equivalent:

This equivalence is called the implication law. It shows that an implication is false only when its antecedent is true and its consequent is false.

• A tautology is a compound proposition that is true for every possible assignment of truth values.
• A contradiction is a compound proposition that is false for every possible assignment of truth values.
• A contingency is a proposition that is true for some assignments and false for others.

Classification:

1. is a tautology because either or its negation must be true. This is the law of excluded middle.
2. is a contradiction because and its negation cannot both be true.
3. is a contingency. It is false when is true and is false, but it is true in the other three cases.

Thus:

Start with

Using the implication law, :

By De Morgan's law:

Using the distributive law:

By the law of excluded middle, :

Using the identity law:

Therefore,

The laws used are the implication law, De Morgan's law, distributive law, law of excluded middle, and identity law.

For the implication :

• Converse:
• Inverse:
• Contrapositive:

The original implication and its contrapositive are logically equivalent:

The converse and inverse are also equivalent to each other:

However, neither the converse nor the inverse is generally equivalent to the original implication.

For example, consider: "If an integer is divisible by , then it is even." Its contrapositive, "If an integer is not even, then it is not divisible by ," is true. Its converse, "If an integer is even, then it is divisible by ," is false, as shown by the counterexample .

A predicate is an open statement containing a variable. It becomes a proposition when the variable is assigned a value or quantified over a specified domain.

• The universal quantifier means "for every" or "for all."

is true precisely when is true for every element in the domain. It is false if at least one element makes false.

• The existential quantifier means "there exists."

is true when at least one element in the domain makes true. It is false when no element in the domain satisfies .

For the domain of integers:

• is true.
• is true because and satisfy it.

The domain is essential because the truth value of a quantified statement can change when the domain changes.

(a) Negation of :

Using the quantifier negation law,

Since ,

Thus, the negation says that there is at least one for which is true and is false.

(b) Negation of :

Applying De Morgan's law gives

Thus, for every , at least one of and must be false.

The order of unlike quantifiers generally changes the meaning and truth value of a statement.

Consider the domain .

First statement:

This says that for every integer , there is an integer such that . It is true because, after is chosen, we can choose .

Second statement:

This says that there is one fixed integer such that for every integer . It is false because no single value of can be the additive inverse of every integer. For example, would require , while would require .

Therefore,

allows the choice of to depend on , whereas

requires one value of to work for all .

A mathematical proof is a logically valid argument that establishes the truth of a proposition from accepted premises.

A well-structured proof normally contains the following elements:

• Statement and domain: Clearly identify what is being proved and the objects under consideration.
• Definitions: Translate important terms into precise mathematical conditions. For example, an even integer has the form for some .
• Assumptions: State the hypotheses of the theorem. In proving , assume .
• Established results: Apply axioms, algebraic laws, definitions, or theorems that have already been proved.
• Logical deductions: Ensure that each step follows from earlier steps by a valid rule of inference.
• Conclusion: Explicitly show that the required statement has been obtained.

A proof must not assume the desired conclusion, rely only on examples, or contain unjustified steps. Clarity is important because a correct proof should allow another reader to verify every deduction.

Let and be arbitrary odd integers.

By the definition of an odd integer, there exist integers and such that

Adding the two equations gives

Simplifying,

Since , the number is also an integer. Therefore, is twice an integer.

By the definition of an even integer, is even. Hence, the sum of any two odd integers is even.

Integers have the same parity when they are both even or both odd. We consider both cases.

Case 1: Both integers are even.

There exist integers and such that

Therefore,

Since is an integer, is even.

Case 2: Both integers are odd.

There exist integers and such that

Then

Since is an integer, is even.

In both possible cases, is even. Hence, integers of the same parity have an even sum.

The statement is

Its contrapositive is

Assume that is odd. By definition, there exists an integer such that

Squaring gives

Rewrite this as

Since is an integer, has the form for some integer . Therefore, is odd.

The contrapositive is true, so the original implication is true. Hence, if is even, then is even.

Both methods establish an implication , but they do so in different ways.

Vacuous proof: Show that the antecedent is false. An implication with a false antecedent is always true, regardless of .

Example: "If an integer is both even and odd, then ." No integer is both even and odd, so the hypothesis is false. Therefore, the implication is vacuously true.

Trivial proof: Show that the consequent is true independently of the antecedent. An implication with a true consequent is always true.

Example: "If an integer is divisible by , then ." For every integer , , and hence . Therefore, the conclusion is always true, making the implication trivially true.

Thus, a vacuous proof establishes , whereas a trivial proof establishes .

The structure of the statement and the available definitions should guide the choice of proof strategy.

• Direct proof: Assume and derive . This is effective when the hypothesis can be translated directly into useful algebraic or logical information.
• Contraposition: Prove . This is useful when provides a more workable condition than , especially in statements involving parity or divisibility.
• Contradiction: Assume and , then derive a contradiction such as . This is useful when the negation of the conclusion creates strong restrictions or when proving nonexistence or irrationality.
• Case analysis: Divide the possibilities into exhaustive cases and prove the result in each case. For integer problems, cases may be based on whether an integer is even or odd.
• Vacuous or trivial proof: Check whether is impossible or is always true before attempting a longer argument.

A good strategy also begins by expanding definitions, identifying relevant theorems, testing examples for insight, and ensuring that the argument proves the original statement rather than merely its converse.

Assume, for contradiction, that is rational. Then it can be expressed in lowest terms as

where , , and .

Squaring both sides gives

so

Thus, is even. Since an integer whose square is even must itself be even, let for some .

Substituting gives

and hence

Therefore, is even, so is also even. Thus, both and are divisible by .

This contradicts the assumption that is in lowest terms. Therefore, the original assumption is false, and is irrational.

To prove a biconditional , both directions must be established:

1. Prove .
2. Prove .

Let be " is odd" and be " is odd."

Forward direction: Assume is odd.

Then for some . Therefore,

Hence, is odd.

Reverse direction: Assume is odd.

Prove this direction by contraposition. If is even, then for some . Thus,

which is even. Therefore, if is odd, cannot be even, so is odd.

Since both directions are true,

A counterexample is a specific instance for which the hypothesis of a universal statement is satisfied but its conclusion is false. A single valid counterexample is sufficient to disprove a universally quantified statement.

(a) Every prime number is odd.

Take the prime number . It is divisible only by and , so it is prime, but it is even. Therefore, is a counterexample, and the statement is false.

(b) If is even, then both and are even.

Take and . Then

which is even. However, is odd, so and are not both even. Thus, is a counterexample.

The correct related statement is: if is even, then at least one of or is even.

A proof of equivalence establishes that two statements always have the same truth value. For statements and , this is usually done by proving both implications:

Alternatively, for propositional expressions, equivalence may be shown using a truth table or established equivalence laws.

A proof by examples is generally not a valid proof of a universal statement. Checking several values only shows that the statement holds for those particular values; it does not cover every element of the domain.

For example, evaluating for many small nonnegative integers produces prime values, but at ,

which is composite.

Examples are useful for:

• developing or testing a conjecture;
• understanding definitions;
• discovering patterns;
• finding counterexamples.

However, a universal claim requires an argument covering arbitrary . In contrast, one counterexample is enough to disprove it.

Error in the attempted proof:

The proof writes immediately after assuming that is even. From evenness, the valid conclusion is only

for some integer . Writing already assumes that is even, which is exactly the conclusion to be proved. Therefore, the argument is circular.

Valid proof by contraposition:

The contrapositive is: if is odd, then is odd.

Assume is odd. Then for some integer . Hence,

Because is an integer, is odd. Thus, the contrapositive is true.

Therefore, if is even, then is even.

Common mistakes in proofs include:

1. Assuming the conclusion: A circular proof uses the desired conclusion as a premise. Avoid this by starting only from the stated hypotheses, definitions, axioms, and previously proved results.

2. Proving the converse: To prove , proving is insufficient. Write the logical form of the statement before beginning and track which proposition is assumed.

3. Using examples as a universal proof: Examples cannot establish . Introduce an arbitrary element of the domain and prove the result without assigning it a special value.

4. Dividing by a possibly zero expression: Cancelling from is invalid unless . State and verify all conditions required by an algebraic operation.

5. Misusing quantifiers: The statements and need not be equivalent. Preserve quantifier order and clearly specify the domain.

Other frequent issues include unjustified steps, ambiguous notation, failing to prove both directions of a biconditional, and treating an implication as false merely because its antecedent is false. A proof should make every logical dependency explicit.