62 votes

What is meant by "logically incorrect"?

Rather than assume what the author means, I consulted the textbook (p. $155$) and examined the excerpt in context... "Logic is the process of deducing information correctly -- it is not the ...
RyRy the Fly Guy's user avatar
20 votes

What exactly does $X - (Y ∪ Z)$ mean?

See the image of your expression in a Venn diagram:
CiaPan's user avatar
  • 13k
16 votes
Accepted

Deriving A, ¬A ⊢ B in a weak Hilbert proof system

Mayhap you missed an additional axiom, or whoever assigned this problem tried to pull a fast one on you? Either way, you cannot derive $A \rightarrow \neg A \rightarrow B$ in the Hilbert system given ...
Z. A. K.'s user avatar
  • 11k
15 votes

Tautologies in classical logic

In Classical Logic it is always the case that either $P$, $\neg P$, or both. You will always be dealing with one of those three options, even if the third never happens. It is also always true for ...
Bram28's user avatar
  • 99.6k
11 votes

What exactly does $X - (Y ∪ Z)$ mean?

Recall that $\cup$ is the set-theoretic counterpart of the logical operator $\vee$ (OR) $\cap$ is the set-theoretic counterpart of the logical operator $\wedge$ (AND) You can also use this identity $ ...
some_math_guy's user avatar
8 votes

Is 1+1=2 logically equivalent to 99+1=100?

The sentence $1+1=2$ is not logically equivalent with $99 +1 =100$. To see this note the way logical equivalence is defined in model theory. In first-order logic two sentences $\varphi, \psi$ of some ...
sequitur's user avatar
  • 1,094
8 votes
Accepted

Why does “propositional calculus” have the word “calculus” in it?

Definition : Douglas N. Clark "DICTIONARY of Analysis, Calculus, and Differential Equations" gives this Entry, with my highlighting and emphasis: calculus (1.) The study of properties of ...
Prem's user avatar
  • 9,030
7 votes
Accepted

Asserting that when (P→Q) and (Q→R) are true, then so is (P→R)

The exercise requires me to show, with the help of truth tables, that if $P\rightarrow Q$ and $Q\rightarrow R$ are true, then $P\rightarrow R$ is true Since we are reasoning completely abstractly, ...
ryang's user avatar
  • 38.8k
7 votes

If P and Q can never be true, are they still "necessary" and "sufficient" for each other?

Clearly, $$(¬P∧¬Q)\implies (\lnot P↔\lnot Q);$$ by contrapositive, $$(¬P↔¬Q)\implies(P↔Q).$$ So, by transitivity, $$(¬P∧¬Q)\implies(P↔Q);$$ that is, $$(¬P∧¬Q)→(P↔Q)$$ is a tautology. After all, ...
ryang's user avatar
  • 38.8k
7 votes
Accepted

What is a logical constant, exactly?

To avoid confusion, it's worth noting that logical constants are not related to the term constant symbol used in mathematical logic when discussing first-order languages, much less to terms such as ...
Z. A. K.'s user avatar
  • 11k
7 votes
Accepted

Disproving a statement by showing that its negation doesn't lead to a contradiction?

$$(¬p\Rightarrow{}\textbf{c})\equiv{p}$$ Also: $\quad(\lnot p{\kern.6em\not\kern-.6em\implies}\bot)\;\equiv\;(\lnot p\land\lnot \bot)\;\equiv\;(\lnot p\land\top)\;\equiv\;\lnot p.$ To conclude that $...
ryang's user avatar
  • 38.8k
7 votes

Can an implication and its converse both be false?

Put $Px$ for $x$ is prime, and $Gx$ for $x > 100$. Now distinguish $\forall x(Px \to Gx) \lor \forall x(Gx \to Px)$ from $\forall x((Px \to Gx) \lor (Gx \to Px))$ The first I think properly ...
Peter Smith's user avatar
  • 54.5k
7 votes
Accepted

Seeking a More Efficient Solution for Knights and Knaves Logic Puzzle

Whenever anyone in a knight-or-knave problem says a statement $P$, we can read it as the guaranteed to be true statement "Either I am a knight and $P$ is true, or I am a knave and $P$ is false.&...
Misha Lavrov's user avatar
7 votes

Is "yesterday it was sunny" a proposition?

As far as mathematical logic is concerned, a proposition is simply whatever you can assign a truth value to. But it doesn’t matter how you do it, what the sentence means and whether your assignment ...
user3840170's user avatar
6 votes

Asserting that when (P→Q) and (Q→R) are true, then so is (P→R)

You ask: But there are also instances where $P\rightarrow R$ is true and $P\rightarrow Q$ and $Q\rightarrow R$ is false. Is this indeed correct or did I do something wrong with the truth table? I ...
Bram28's user avatar
  • 99.6k
6 votes
Accepted

In a direct proof, do your chain of deductions have to involve the antecedent in any way in order for this to be considered a "direct proof"?

A direct proof is simply a proof whose assumptions are drawn from just the set of axioms, established theorems and other givens. This is not to say that a direct proof (actively) assumes any ...
ryang's user avatar
  • 38.8k
6 votes

Should I completely forget about the meaning of if-then sentences as used in ordinary language and assign them a new meaning?

We go to Jack and Jill's party in April. Later we can't remember whose birthday was being celebrated. But I tell you that I think Jill has an autumn birthday. So you say "Ah, if Jill has an ...
Peter Smith's user avatar
  • 54.5k
6 votes
Accepted

On the tautology $(P \implies Q) \vee (Q \implies P)$

Yes, it is always true. I guess you are thinking about real life examples and that is confusing you because of the time dimension added to the situation. For instance: Let $Q$ be "I eat" and ...
Daniel Hidalgo Chica's user avatar
6 votes
Accepted

Tautologies in classical logic

"According to its truth table, $P \lor \lnot P$ is a tautology, i.e. it is true for all truth values of its constituent propositions." OP is missing the Point that the constituent ...
Prem's user avatar
  • 9,030
5 votes
Accepted

Context on the theory of category theory

As Alex says in the comments, you can use two-sorted first order logic for this, with a sort for objects and a sort for morphisms. But actually this is technically unnecessary, and (small) categories ...
Qiaochu Yuan's user avatar
5 votes
Accepted

Why is $((p \land q) \Rightarrow z) \Rightarrow (p \Rightarrow z) \lor (q \Rightarrow z)$ true?

The sentences \begin{align}\Big((P \land Q) → Z\Big) → \Big((P → Z) \lor (Q→ Z)\Big)\tag{✔️1}\end{align} and \begin{align}∀\color{green}n\bigg(\quad\Big(\big(P\color{green}n ∧ Q\color{green}n\big) → Z\...
ryang's user avatar
  • 38.8k
4 votes
Accepted

How to prove that if $P, \mathord{\sim}Q\vdash\bot$, then $P\vdash Q$

Strictly speaking, ripped out of context, $P \vdash Q$ doesn't have a determinate meaning. It is like “Jill is before Jack". In what way? On the class list? In who gets to bowl first? In order of ...
Peter Smith's user avatar
  • 54.5k
4 votes
Accepted

If $P \implies Q \implies R$ holds, does it follow that $\lnot R \implies \lnot Q \implies \lnot P$ is also true?

You want to be a little careful in not confusing logical notation with mathematical notation. In particular, the logical operator called the material implication (more often written using $\to$ rather ...
Bram28's user avatar
  • 99.6k
4 votes
Accepted

If P and Q can never be true, are they still "necessary" and "sufficient" for each other?

In mathematics, "P is necessary for Q" is defined as meaning "it is impossible for P to be false and Q to be true." If both P and Q are totally impossible, then it's certainly ...
Tanner Swett's user avatar
  • 10.1k
4 votes
Accepted

Does $\Gamma \vDash \alpha \iff \Gamma \vDash \beta$ implies $\alpha \iff \beta$?

No it doesn't. Example: whenever p is true then p or q is true. Whenever p is true p is true. But it is not true that p iff p or q.
Porky's user avatar
  • 725
4 votes

What is the relationship between ultrafilters and propositional theories?

The relationship is Boolean algebras A filter in a boolean algebra corresponds $1:1$ with surjective homomorphisms from that algebra to a some other algebra. An ultrafilter in a boolean algebra ...
Chad K's user avatar
  • 4,321
4 votes
Accepted

What is meant by "logically incorrect"?

And If I said "Socrates is a Martian and Martians live on Pluto, therefore 2 + 2 = 4" then what I said was logically incorrect. I agree with your observation that this implication is (...
ryang's user avatar
  • 38.8k
4 votes
Accepted

Are the derivations of a consistent set a consistent set?

$\Omega$ is indeed a consistent set of formulas. In other words, it is indeed possible for all formulas in $\Omega$ to be simultaneously true. This is because every formula $\varphi \in \Omega$ is a ...
RyRy the Fly Guy's user avatar
4 votes
Accepted

Short proof of the principle of explosion in propositional calculus

To save us from parenthesis hell, let's follow the proof-theory convention of writing $P \rightarrow (Q \rightarrow R)$ as $P \rightarrow Q \rightarrow R$. We can write down a short, seven-line proof ...
Z. A. K.'s user avatar
  • 11k
4 votes

Exclusive Or vs Inclusive Or

Contrary to popular belief, the use of 'either' does not necessarily mean that you are dealing with an exclusive or ... and the lack of 'either' does not mean you are dealing with an inclusive or. ...
Bram28's user avatar
  • 99.6k

Only top scored, non community-wiki answers of a minimum length are eligible