Tagged Questions

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)

1
vote
1answer
49 views

How to solve a propositonal task question like this?

Hi guys i got a task in propositional logic im a bit stuck in. Here is the task: Let the statement variables be: $H:$ "I ​​eat honey» $M:$ "I ​​drink milk" $B:$ "I ​​eat bread" a) Represent the ...
2
votes
1answer
46 views

How does one get rid of $ p $?

How does one get rid of $ p $ in $(p\Leftrightarrow q) \wedge (p\Leftrightarrow r) $? I have already tried to simplify the formula, applied DeMorgan's laws, etc, but nothing helps. Does anyone know ...
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 ...
1
vote
1answer
746 views

Induction proof for the lengths of well-formed formulas (wffs)

Use induction to show that there are no wffs of length 2, 3, or 6, but that any other positive length is possible. The wffs in question are those associated with sentential/propositional logic. So, ...
0
votes
3answers
244 views

Qns on Propositional Logic - Inference Rules + Logical Equivalence

Have been working on this for the past 2 hours and still not getting any where. Any help will be much appreciated! Consider the following argument 1) p 2) p v q 3) q → (r → s) 4) t → r ∴¬s → ¬t ...
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
2answers
209 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 ...
3
votes
2answers
107 views

Question about Logical implication

Suppose $A$ is a set of propositional formulas, and suppose $\varphi$ is a propositional formula. In my textbook they write $A \models \varphi$, if for every truth assignment $w$ such that $w(\psi) = ...
4
votes
1answer
132 views

Definition by Recursion

I just started studying logic, not as a course at a university, but as pastime. Since I do not study logic at an institution I use many different textbooks, including Enderton's $A$ $Mathematical$ ...
0
votes
1answer
2k views

Mathematical Logic: Propositional Logic; First Order Logic.

I need good book of Mathematical Logic for gate 2014 exam. GATE syllabus is "Mathematical Logic: Propositional Logic; First Order Logic". Thank you.
1
vote
1answer
58 views

Where can I learn more about these two functions obtained from IFF and XOR?

Given a set $X$, write $\mathrm{heaps}(X)$ for the set of all finite heaps (or 'multisets', if you prefer) on $X$. Under this definition, it is well-known that if a binary operation $*$ on a set $X$ ...
4
votes
1answer
90 views

Can we convert this statement about sets into a statement of propositional logic?

A question was just asked here about proving $$A⊆(B∪C)⟺A\setminus C⊆B.$$ We can prove this statement directly, using the concepts of first-order logic. "Suppose $x \in A \setminus C$ and that ...
6
votes
1answer
835 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 ...
2
votes
2answers
179 views

Proving and Modeling Logical Consistence

Suppose I have a finite list of logical statements (would these be called axioms?) and for the sake of discussion say that there are 6 such statements. All statements are in the form of propositional ...
3
votes
3answers
168 views

Are statements like “Every time I've done X, Y has happened” (vacuously) true if I've never done X?

I've recently been wondering about vacuous truths. I know a statement like "I've never been beaten in a race" is true if I've never been in a race, but what I'm wondering is if the following ...
6
votes
7answers
361 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 ...
1
vote
2answers
289 views

Two questions about monotonicity of entailment.

I wonder about two things. First, how do we prove that entailment in some logic is monotonic? The second one - What is the relationship between monotonicity of logic and deduction theorem? It seems ...
-1
votes
3answers
95 views

the negation of $A \veebar B \veebar C $??

I need to know the negation of $A \veebar B \veebar C $, with $\veebar$ thanks in advance!!
3
votes
3answers
363 views

Simplify a proposition of logic: $p ∨ (p ∧ (\lnot p ∧ q ∨ r ∧ (p ∧ r)))$

I'm trying to come up with some concrete simplification for the following proposition: $$p ∨ (p ∧ (\lnot p ∧ q ∨ r ∧ (p ∧ r)))$$ Any ideas on what is the resulting form?
0
votes
2answers
59 views

Mathematical Logic : Implication

consider the statement, if today is Monday then tomorrow is Tuesday how is the third condition true in this case?
2
votes
3answers
589 views

Rule of Replacement and Rule of Inference

My question is how I can solve this argument. Can you please help me? $(V\implies \lnot W)\land(X\implies Y)$ $(\lnot W\implies Z)\land(Y\implies\lnot A)$ $(Z\implies\lnot B)\land(\lnot A\implies ...
-1
votes
1answer
72 views

Epistemic disjunction, axiom or rule?

Assume I have a minimal logic |- with disjunction v and implication ->. Now I want to represent some domain knowledge. One opponent says I should represent it as an axiom: ...
1
vote
1answer
440 views

Is first-order logic more expressive than propositional logic with infinite statements?

I read that the difference between propositional logic and first-order logic is that in the latter, we can quantify over individual objects. However, if infinitely long statements are allowed, it ...
-4
votes
1answer
53 views

Propostional Functions

Let $P$ stand for the set of people and let $p \in P$. $C(p)$ is a propositional function that is true when person $p$ plays cricket; $R(p)$ is a propositional function that is true when $p$ plays ...
3
votes
4answers
939 views

How to prove Disjunction Elimination rule of inference

I've looked at the tableau proofs of many rules of inference (double-negation, disjunction is commutative, modus tollendo ponens, and others), and they all seem to use the so-called "or-elimination" ...
3
votes
4answers
102 views

Validate an argument with if and only if

How would I validate this argument? $p \iff q$ $r \vee q$ $\neg r$ $\overline{\therefore \neg p\quad}$ Is this Valid or Invalid? I would say this argument is invalid, because r or q doesn't ...
2
votes
3answers
409 views

Determine whether the argument is valid or invalid

$\;(\lnot p \lor q)\land (\lnot p \rightarrow q)$ $\;\;\;\;p$ $\overline{\therefore\;\lnot q\qquad}$ Valid or invalid: How would I approach this problem? Thanks for the help.
5
votes
3answers
127 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 ...
1
vote
2answers
72 views

Disjunction Form

I'm a little stuck on finding an equivalent disjunctive form to $P \rightarrow (Q \rightarrow \neg P \wedge R) $. I have only gotten $\neg P \vee Q (\neg P \vee Q) \wedge (\neg P \vee R) $. But I ...
3
votes
2answers
63 views

Is there a name for this property of XOR?

I noticed that XOR ($\oplus$) has a somewhat "mutualistic" property: $\left(\left(A \oplus B\right)\iff C\right) \iff \left(A \iff \left(B \oplus C\right)\right)$ This can be easily checked via a ...
3
votes
2answers
135 views

Understanding the definition of soundness

Definitions, as far as I understand them: A formal system is sound if $\vdash A$ implies $\vDash A$. Semantic entailment $\vDash A$ means that in every model of this system (that is, on every ...
5
votes
3answers
163 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 ...
1
vote
3answers
115 views

Proving statements like $(a\Rightarrow b) \Rightarrow (p \Rightarrow q)$.

Is there a way to simplify this sort of statement? For example, $$a \Rightarrow (b\Rightarrow c)$$ is equivalent to $$(a \wedge b) \Rightarrow c.$$ I'm looking for something similar for ...
8
votes
3answers
661 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?
1
vote
1answer
57 views

is this the right truth table?

When I filled out the table I tried my best to figure it out. But If I made any mistakes please help me correct them. Thanks! sorry 5th one should be false
1
vote
1answer
160 views

Are my answers right here about true and false statements?

Every integer is a rational number -> false -- correct? Let r = true; s = true. Is this statement true or false? $$\lnot [r \lor (\lnot s \lor r)];\quad$$ -> true -- correct? Let p = true; r = ...
0
votes
1answer
44 views

Is this the right truth table information?

I'm constructing a truth table and these are the values I put in. Am I right here or have I made any mistakes? All help is highly appreciated.
1
vote
2answers
141 views

The definition of logical implication.

Is the following definition correct? I think it is not. "A proposition $P_1$ implies another proposition $P_2$ if $P_2$ is true when­ever $P_1$ is true". Comprehensive Mathematics for Computer ...
1
vote
2answers
51 views

Math logic - determine whether an inference exist

This is the first time I see this kind of question. Ok, I have: $\{\neg A \vee B, B \to C, A \vee C \} \models B \vee C$ I have to determine whether an inference exist or not. How do I do so? ...
0
votes
1answer
43 views

Do There Exist Normal Multi-Valued Interpretations for the Equivlaential Calculus?

Suppose we define a propositional calculus, just by its (object language) theorem set and its rules of inference. For example, suppose we define the C-N propositional calculus by the set of theorems ...
0
votes
1answer
62 views

Analog of modus ponens for semantics

To pose my question, I first must first quickly define a language, a model, semantics for such models, and a logical system called S4O. Consider a language $L$ with a set $PV$ of propositional ...
4
votes
3answers
116 views

Basic logical math properties

So I have a question in logical math. I want to know how to simplify the next expression and maybe understand the rule. So I have those 3 atomic formulas $A,B,C$ (if there is a way) $$ ...
4
votes
2answers
236 views

Logical systems that are complete but not sound

I was wondering, are there any commonly used logics(with both notions of deductions and of semantics) that are complete but not sound? I'm looking for an example that has actually proven useful to ...
2
votes
2answers
54 views

To which (logical) language belongs $\{p\} \Rightarrow q$?

According to my book, the essential difference between a logical implication $\{p\} \Rightarrow q$ and the statement $p \to q$ is that $p \to q$ is part of the propositional language, and $\{p\} ...
20
votes
4answers
464 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 ...
0
votes
2answers
80 views

using the conditional to abbreviate formulas

i hope you're all doing well. I was reading a paper recently that started out with a language $L$ with a set $PV$ of propositional variables, Boolean connectives $\neg, \vee$, and some modalities ...
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 ...
2
votes
1answer
108 views

Gap in Halmos & Givant's “Logic as Algebra”: undefined $\models$?

I have been hugely enjoying Logic as Algebra by Halmos and Givant (1998, isbn: 0-88385-327-2)1, largely because I appreciate the authors' careful attention to the ...
2
votes
1answer
61 views

a fundamental clarification about predicate expression (formula)

I have few foundation questions to be clear about expression involving predicates. $\forall n\in \Bbb N.p(n) \tag {1.2}$ Here the symbol $\forall$ is read “for all.” The symbol $\Bbb N$ ...
0
votes
1answer
228 views

Definition of logical equivalence

I'm following a book on Discrete Mathematics, and am having trouble understanding a nuance. Two statement forms are called logically equivalent if, and only if, they have identical truth values ...