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
2answers
389 views

(Symbolic Logic) Proving P v P = P (Idempotency) using a direct proof

Ok, so it's very easy to show P v P = P (where = is logically equivalent) using a truth table as well as using a conditional proof. P v P Premise ~p Assumption p Disjunctive ...
1
vote
1answer
91 views

Logical equivalence question

$(M \vee B) \wedge (H \vee B) \wedge (H \vee M)$ is a formula where $\wedge$ is the symbol for AND. What I need to know is: is there any equivalent formula to this one?
0
votes
1answer
1k views

A Proof relating to the Disjunctive normal form

Here is a problem from Kenneth Rosen's Discrete Mathematics and its Applications, Section 1.3 Suppose that a truth table in $n$ propositional variables is specified. Show that a compound ...
3
votes
0answers
71 views

Application of the compactness theorem

In my logic book they ask me to prove the following as a consequence of the compactness theorem for propositional logic. Let $S \subseteq N$ be an infinite set. I have to show that there exists an ...
1
vote
3answers
286 views

Propositional logic: Finding a formula F with statement variables from truth table

I need to find a formula for $F$ with statement variables $H, M$ and $B$ such that the truth table for $F$ looks as follows: Does anyone know a cool and/or easy way to solve problems like this? ...
0
votes
1answer
117 views

Constructing Proof Trees for Natural Deduction

I'm in the process of learning the process of writing so-called proof trees for $\textit{Natural Deduction}$. One question that I still grapple with is the actual process According to Van Dalen ...
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
748 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
249 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
91 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
844 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
181 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
292 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
365 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
594 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
945 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
165 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
664 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
161 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
142 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
240 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\} ...