Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

learn more… | top users | synonyms (1)

41
votes
17answers
3k views

In classical logic, why is$ (p\Rightarrow q)$ True if both p and q are False?

I am studying entailment in classical first-order logic. The Truth Table we have been presented with for the statement $(p \Rightarrow q)\;$ (a.k.a. '$p$ implies $q$') is: ...
20
votes
4answers
479 views

Associativity of $\iff$

In this answer, user18921 wrote that the $\iff$ operation is associative, in the sense that $(A\iff B)\iff C$ $A\iff (B\iff C)$ are equivalent statements. One can brute-force a proof fairly ...
16
votes
5answers
522 views

If both $P$ and $Q$ are true , how can I tell that $P$ implies $Q$?

I am trying to understand the fundamentals of mathematical logic in order to be able to study discrete mathematics and computer science soon. I have a big problem understanding Implication. I ...
15
votes
8answers
2k views

Assumed True until proven False. The Curious Case of the Vacuous Truth

Given two statements, $P$ and $Q$, and the logical connective, $\implies$, the truth table for $P \implies Q$ is: $$\begin{array}{ c | c || c | } P & Q & P\Rightarrow Q \\ \hline \text T ...
12
votes
1answer
948 views

Minimum number of different clues in a Sudoku

I wonder if there are proper $9\times9$ Sudokus having $7$ or less different clues. I know that $17$ is the minimum number of clues. In most Sudokus there are $1$ to $4$ clues of every number. ...
12
votes
2answers
1k views

Do De Morgan's laws hold in propositional intuitionistic logic?

In Wikipedia page on intuitionistic logic, it is stated that excluded middle and double negation elimination are not axioms. Does this mean that De Morgan's laws, stated $$ \lnot (p \land q) \iff ...
11
votes
3answers
692 views

In axiomatization of propositional logic, why can uniform substitution be applied only to axioms?

I'm reading an introductory book about mathematical logic for Computation (just for reference, the book is "Lógica para Computação", by Corrêa da Silva, Finger & Melo), and would like to ask a ...
10
votes
8answers
9k views

Not understanding this row of truth table for logical implication

Provided we have this truth table where "$p\implies q$" means "if $p$ then $q$": $$\begin{array}{|c|c|c|} \hline p&q&p\implies q\\ \hline T&T&T\\ T&F&F\\ F&T&T\\ ...
10
votes
5answers
1k views

What is a false premise?

I don't understand what a sound argument is. And what does it mean for a premise to be false? Why does case 3 (A is false, B is true) not apply in the real world? Here the author says that the first ...
10
votes
2answers
412 views

What is the converse of this statement and is it true?

If $a$ and $b$ are relatively prime, $a\mid c$ and $b\mid c$, then $(ab)\mid c$. I am lost. Would the converse be "If $(ab)\mid c$, then $a$ and $b$ are relatively prime and $a\mid c$ and $b\mid c$" ...
10
votes
2answers
107 views

Mystery Men Movie - Propositional Logic

In the movie Mystery Men, there is this scene: Captain Amazing (good guy): I knew you couldn't change. Casanova Frankenstein (bad guy): I knew you'd know that. Captain Amazing: Oh, I know. And ...
9
votes
8answers
941 views

I can't understand logical implication

I just started studying logic (high school) anyway...for the truth table of logical implication If sentence $A$ is true and $B$ is true then $A\implies B$ is true. does that mean if $A$ and $B$ are ...
8
votes
3answers
209 views

How to deduce that something does not follow?

Assume I have formulas $H$, $P$ and $Q$. Assume further that I can show in classical logic that $P$ follows from $H$: $$H \vdash P$$ And that the negation of $Q$ follows from $H$: $$H \vdash \neg ...
8
votes
2answers
13k views

How to convert to conjunctive normal form?

If i have a formula: $((a \wedge b) \vee (q \wedge r )) \vee z$, am I right in thinking the CNF for this formula would be $(a\vee q \vee r \vee z) \wedge (b \vee q \vee r \vee z) $? Or is there some ...
8
votes
7answers
4k views

Associativity of logical connectives

According to the precedence of logical connectives, operator $\rightarrow$ gets higher precedence than $\leftrightarrow$ operator. But what about associativity of $\rightarrow$ operator? The implies ...
8
votes
3answers
706 views

Why Peirce's law implies law of excluded middle?

Why if in a formal system the Peirce's law $((P\rightarrow Q)\rightarrow P) \rightarrow P$ is true, the law of excluded middle $P \lor \neg P$ is true too?
7
votes
5answers
1k views

Help to understand material implication

This question comes from from my algebra paper: $(p \rightarrow q)$ is logically equivalent to ... (then four options are given). The module states that the correct option is $(\sim p \lor q)$. ...
7
votes
5answers
1k views

Is $(p \to q) \to r$ logically equivalent to $p \to (q \to r)$?

Is $(p \to q) \to r$ logically equivalent to $p \to (q \to r)$? I try to simply each one, I got $\lnot ( \lnot p \lor q) \lor r$ and $\lnot p \lor ( \lnot q \lor r)$ respectively, then I am stuck. ...
7
votes
6answers
1k views

How to demystify the axioms of propositional logic?

How might I go about getting some intuition on the typical axiom schemes given for propositional logic? They seem rather mysterious at first glance. For example, these are taken from: ...
7
votes
4answers
177 views

How or why does intutionistic logic proof negations from within the theory, constructively?

I'm having a little of a cognitive dissonance why, in intuitionistic logic, it's possible to show stentences like $(\neg A \land \neg B) \implies \neg(A\lor B).$ In plain text: If 'A isn't true' as ...
7
votes
2answers
210 views

My professor says this is NOT a typo, but this does not appear to be logically valid.

$$\begin{array}{rlll} 1. & \sim H\lor \sim G & \text{Premise} & \\ 2. & H\& (G\lor H) & \text{Premise} & \text{DEDUCE $F\& H$} \end{array}$$ Using the rules ...
7
votes
2answers
1k views

Proof of the Compactness Theorem for Propositional Logic

I have a problem understanding the proof for the compactness theorem for propositional logic in my logic course. The compactness theorem states that there is a model for an infinite set $S$ of ...
6
votes
4answers
396 views

Equivalence of $a \rightarrow b$ and $\lnot a \vee b$

Is there a proof for the logical equivalence of $a \rightarrow b$ and $\lnot a \vee b$?
6
votes
7answers
363 views

Intuition behind “If P then Q” = “Q or Not P ”

I understand with truth tables the Conditional Law: $[P \Longrightarrow Q] \equiv [\lnot P \vee Q]$. However, what's the intuition or a natural motivation? Source 1, all but intuitive, now appears as ...
6
votes
5answers
234 views

Overlap of Propositional Logic and Elementary Set Question

I am a bit stuck on a basic sets problem: We know from resolutions that $(p \lor q) \land (\neg p \lor r) \to q \lor r$. Use this fact to show that $(P \cup Q) \cap (\overline{P} \cup R) \subseteq ...
6
votes
5answers
623 views

Logical NOT of an implication

I was looking through my notes but I was unable to find the answer to this, which I need to start am assignment question. What would the following be, in terms on moving the negation inside the ...
6
votes
3answers
10k views

De-Morgan's theorem for 3 variables?

The most relative that I found on Google for de morgan's 3 variable was: (ABC)' = A' + B' + C'. I didn't find the answer for my question, therefore I'll ask here: ...
6
votes
8answers
693 views

General form of a proof that $ab=0 \implies a=0 \lor b=0$

When proving that $ab = 0 \implies a = 0 \,\mbox{ or }\,b = 0$ for members $a$ and $b$ of a field, I used an argument like Suppose $ab = 0$ and $a \ne 0$ ... then $b = 0$. Now suppose $ab = 0$ and ...
6
votes
3answers
318 views

How complicated is the set of tautologies?

Consider the set $\mathcal T$ of all tautologies in the propositional calculus in which the only operators allowed are $\to$ and $\neg$, and involving only the two variables $x$ and $y$. How ...
6
votes
5answers
194 views

Is a proposition about something which doesn't exist true or false?

Let S = {x | x is not an element of x } The set S doesn't exist. Then, would a proposition such as "The cardinality of S is 1," be true or false? Equivalently, I could have made a proposition, "the ...
6
votes
5answers
213 views

The deep structure of logical formulas

A long-standing question to which I never found a concise answer is: Is there something like an unambiguous deep structure of a formula of propositional logic, opposed to its comparingly ...
6
votes
2answers
291 views

Is this a valid proposition?

Consider following two sentences. $x^2 = 1.$ Today is Thursday. The first statement can't be a proposition. because the truth of (1) depends on the value of $x$. For some values of $x$ it is true ...
6
votes
1answer
270 views

distribution of categorical product (conjunction) over coproduct (disjunction)

In the classical and intuitionistic propositional calculi, it is straightforward, using natural deduction, to derive $((A \land C) \lor (B \land C))$ from $(A \lor B) \land C$: Assume $(A \lor B) ...
6
votes
3answers
165 views

Equivalence relation using tableaux

How can I prove that two formulae are equivalent using analytic tableaux? For example, how can I prove the following theorem? $$ (p \rightarrow q) \equiv (\neg q \rightarrow \neg p)$$
6
votes
1answer
219 views

Unique decomposition of wffs when left and right parentheses are indistinguishable

I'm working through Enderton's book A Mathematical Introduction to Logic 2nd Edition for self study. Section 1.3 Exercise 7 Suppose that left and right parentheses are indistinguishable. Thus, ...
6
votes
1answer
908 views

Relationship between propositional logic, first-order logic, second-order logic higher-order logic, and type theory

I understand there is propositional logic, first-order logic, second-order logic higher-order logic, and type theory, where the latter logics are extensions of the former logics. Can someone explain ...
6
votes
4answers
2k views

Express logic puzzles with proposition calculus notation

I’m trying to solve a logic puzzle that goes like this: The police have three suspects for the murder of Mr. Cooper: Mr. Smith, Mr. Jones, and Mr. Williams. Smith, Jones, and Williams each declare ...
5
votes
3answers
423 views

Modus Ponens vs implication?

What is the difference between Modus Ponens and an implication? If so, could you please give a simple example to help understanding?
5
votes
4answers
342 views

Counterexample for $(p\rightarrow q) \longleftrightarrow (!q \rightarrow\mathord !p) $

Is the statement $$(p\rightarrow q) \longleftrightarrow (!q \rightarrow \mathord!p) $$ always true? If it is not, provide a counterexample. Till now I cannot find a counterexample nor prove that ...
5
votes
2answers
2k views

What's the difference between a negation and a contrapositive?

What's the difference between a negation and a contrapositive? I keep mixing them up, but it seems that a contrapositive is a negation where the terms' order is changed and where there is an imply ...
5
votes
3answers
130 views

proving logical equivalence $(P \leftrightarrow Q) \equiv (P \wedge Q) \vee (\neg P \wedge \neg Q)$

I am currently working through Velleman's book How To Prove It and was asked to prove the following $(P \leftrightarrow Q) \equiv (P \wedge Q) \vee (\neg P \wedge \neg Q)$ This is my work thus far ...
5
votes
4answers
251 views

When $\;\text{FALSE}\implies P(x),\;$ is $P(x)\;$ false?

Say we know that $P(k) \implies P(k+3)$. Then if we know $P(1)$ is true, we know $P(4), P(8) \dots$ are also true. However if we know $P(1)$ is false, does that mean $P(4), P(8) \dots$ are also ...
5
votes
2answers
2k views

What is the difference between necessary and sufficient conditions?

If $\quad p \implies q\quad $ ($p$ implies $q$), then $p$ is a sufficient condition for $q$. If $\quad \bar p \implies \bar q \quad$ (not $p$ implies not $q$), then $p$ is a necessary condition for ...
5
votes
8answers
338 views

How can I Prove that $[(p \to\neg q) \wedge q] \to \neg p$ is a tautology?

Prove that $[(p \to\neg q) \wedge q] \to \neg p$ is a tautology Laws of logic I tried prove it by using truth table but it didn't produce a tautology. This is my work so far: $$ [(p \to \neg ...
5
votes
4answers
639 views

What is a constructive proof of $\lnot\lnot(P\vee\lnot P)$?

Glivenko's theorem says that $\lnot\lnot P$ is a theorem of intuitionistic logic whenever $P$ is a theorem of classical logic. Is it closely related to the so-called Gödel–Gentzen negative translation ...
5
votes
1answer
212 views

If $x\rightarrow y$ and $y \rightarrow z$, prove, by contradiction, that $x \rightarrow z$

Say you're given $$x\Rightarrow y$$ $$y\Rightarrow z$$ Prove that $x\Rightarrow z$ by contradiction. It seems like such a simple task, because it's easy to evaluate that it must be true. But I ...
5
votes
2answers
100 views

Is there a logical interpretation for equalizer and co-equalizer?

I know the logical equivalent to several universal constructions. For example product $\times$ is $\land$ and co-product $+$ is $\lor$. The associated arrows are projection and inclusion. The ...
5
votes
3answers
146 views

Can Peirce's Law be proven without contradiction?

Good evening, I heard the proof by contradiction is required for Peirce's law. AFAIK, truth tables are not related directly to proofs by contradiction, and if of an operation $\text {op}$ we have a ...
5
votes
3answers
169 views

Help in writing contraposition

Usually I find it a cakewalk to write the contrapositive, but the following statement is quite complex for the task: For all integers $n > 1$, if $n$ is not prime, then there exists a prime ...
5
votes
1answer
284 views

What are a list of helpful boolean identities for solving boolean functions?

For instance, things like $P \Leftrightarrow Q \equiv (P \Rightarrow Q) \land (Q \Rightarrow P)$ is a very helpful formula to know, as is $P \Rightarrow Q \equiv \lnot P \lor Q$ is another helpful ...