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
46 views

Proof of Soundness Lemma

We are given that $\Gamma \vdash \phi$ and want to show that for any truth assignment $\nu$ such that $\bar{\nu}(\psi) = T$ for all $\psi \in \Gamma$ then $\bar{\nu}(\phi)=T$ We are given the hint to ...
1
vote
1answer
21 views

Inference Lemma Proof?

Suppose that $\Gamma$ is a subset of $\mathcal{L_0}$, $\phi$ and $\psi$ formulas. If $\Gamma \vdash \psi$ and $\Gamma \vdash (\psi\to \phi)$ then $\Gamma \vdash \phi$. Proof: Let $\langle ...
0
votes
1answer
38 views

Properties that can be proven with induction on wff's?

Let $\mathcal{L_0}$ be the smallest set $L$ of finite sequences of $\textit{logical symbols}= \{(\enspace)\enspace\neg\to\}$ and $\textit{propositional symbols}=\{A_n\mid n\in\mathbb{N}\}$ for $n \in ...
1
vote
1answer
58 views

Translate the following sentence into conjunctive normal form

"Anyone who has cats as pets will not have mice": $$\forall x[\exists zHave(x,cat(z))]\rightarrow \forall y[\neg Have(x,mouse(y))]$$ I need to translate this into conjunctive normal form. So the ...
0
votes
1answer
59 views

Prove that John is not a light sleeper

Define each sentence in terms of CNF. Prove that John is not a light sleeper. ...
1
vote
2answers
32 views

What operation is done first in the following exercise…

Here I have such an exercise: I have to simplify the form of the following expression:$$(p\lor \lnot q)\land(\lnot p \lor q )\lor (p \lor \lnot r)\lor \lnot q$$. I know how to simplify it, but what ...
0
votes
1answer
58 views

Why do you only need to show validity in one world when using trees in institutionist/constructivist logic?

Depicted below, my prof used a tree to prove that an argument is valid according to intuitionist logic. However, I can't find a contradiction in world 0. Why is invalidity ascertained when all ...
4
votes
2answers
222 views

Proof that expression is a tautology

I'm studying to my exam and I have some doubts. The expression: $$¬(P \Leftrightarrow Q) \Leftrightarrow P \oplus Q$$ The objective is to know if it is a tautology. I don't know the result. I made ...
0
votes
1answer
33 views

Propositional Logic meta-variable notation abuse

When defining Formation Sequence, van Dalen (4th edition page 9) says: A sequence $(\varphi_0,\varphi_1,...,\varphi_n)$ is called a formation sequence of $\varphi$ if $\varphi_n=\varphi$ and: ...
0
votes
2answers
38 views

Simplify a logic expression

I'm studying to my exam and I have some doubts. The expression: ¬(P ∨ Q) ∨ (¬P ∨ Q) The result: ¬P ∨ Q The objective is to simplify. I'm stuck at (¬P ∧ ¬Q) ∨ ¬P ∨ Q I could make the distributive, ...
0
votes
1answer
28 views

Simplify a logic expression

I'm studying to my exam and I have some doubts. The expression: $$ \lnot \lnot P \land \lnot(\lnot\lnot Q \lor\lnot P) $$ The result: $$ P \land \lnot Q $$ The objective is to ...
1
vote
2answers
49 views

prove $[¬p\land (p\lor q)]→q ≡ T$ without using the truth table

I need to prove $[¬p\land (p\lor q)]→q ≡ T$ without using the truth table. Please help me to solve it.
0
votes
1answer
38 views

show that $(p \to q) \vee (p \to r) \to (q \vee r)$ and $p\vee q\vee r$ are logically equivalent [duplicate]

without using the truth table: Show that $(p \to q) \vee (p \to r) \to (q \vee r)$ and $p\vee q\vee r$ are logically equivalent.
1
vote
2answers
66 views

Prove $\;\big((p\rightarrow q) \lor (p \rightarrow r)\big) \rightarrow (q\lor r)\equiv p \lor q \lor r$ without use of a truth table.

Without using the truth table, I need to prove: $$\big((p\rightarrow q) \lor (p \rightarrow r)\big) \rightarrow (q\lor r)\equiv p \lor r \lor q$$ Up until now, we've been using truth-tables to ...
1
vote
2answers
37 views

Building logical connectives only with $\neg$ and $\to$

We want to show that the only connectives that are absolutely necessary are $\neg$ and $\to$. Meaning we can construct all the others with them. Given $A_1, A_2 \in \mathcal{L_0}$, the set of ...
0
votes
2answers
39 views

Characterizing the collection of automorphisms on $\mathbb{Z}$ with a binary relation.

How can one characterize the collection of automorphisms of integers $\mathbb{Z}$ with the binary relation "$<$"? Or "$>$"? "$=$"? How can we acquire the collection of automorphisms?
0
votes
3answers
78 views
2
votes
2answers
98 views

Proving tautology

Trying to prove if this statement is a tautology: $\neg (p\to q) \to p$ I can simplify the left hand side $\neg (p\to q)$ to $p\land \neg q$, but once I get there I'm stuck.
0
votes
0answers
29 views

How Do I Show that Condensed Derivable Rules of Inference Yield the Same Formula as Using Condendensed Detachment Multiple Times?

If we look at condensed detachment of two formulas $\alpha$ and $\beta$, we can see that D$\alpha$.$\beta$, where $\alpha$ has form C$\alpha$$_a$$\alpha$$_b$ is equivalent to using the rule ...
4
votes
1answer
44 views

Show that $\Gamma \cup \{\neg \phi\}$ is satisfiable if and only if $\Gamma\not \models \phi$

Let $\Gamma$ be a set of formulas and $\phi$ be a formula. Show that $\Gamma \cup \{\neg \phi\}$ is satisfiable if and only if $\Gamma\not \models \phi$. This seemed pretty obvious but I wanted ...
1
vote
1answer
116 views

Discrete mathematics Logic Proof

I'm stuck with these problems... ...
0
votes
1answer
49 views

Propositional formulas, truth assignments proof

Exhibit a propositional formula $\phi$ using only the logical connectives $\neg$ and $\to$ and using all three propositional symbols $A_1,A_2,A_3$ such that for any $\nu$, $\bar{\nu}(\phi)= T \iff \nu ...
2
votes
1answer
40 views

Using semantic tableaux to prove a situation can occur

I am having a wedding and want to prevent fights at the wedding. suppose the following: John will attend if mark or Aston attends. Aston attends if Mark does not Attend If Aston attends, john will ...
2
votes
1answer
80 views

Propositional Calculus: Stating and proving the unique readability theorem in Polish notation

The Language $\mathcal{L_0}$: Let $\mathcal{L_0}$ be the smallest set $L$ of finite sequences of $\textit{logical symbols}= \{(\enspace)\enspace\neg\}$ and $\textit{propositional ...
1
vote
2answers
51 views

Propositional Calculus: Stating and verifying readability and unique readability of a given language $\mathcal{L^*}$

Problem: Consider the set of symbols * and #. Let $\mathcal{L^*}$ be the smallest set $L$ of sequences of these symbols with the following properties: a) The length one sequences ...
1
vote
1answer
36 views

Is $A \vee B$ in its Conjunctive Normal Form?

Since a conjunctive normal form consists of a conjuction of disjunctions, why is, say, $A \vee B$ in the conjunctive normal form?
0
votes
4answers
61 views

Basic question on logic

I have a slight problem in solving the following question. Let $P$ and $Q$ be statements. Which of the following strategies is "NOT" a valid way to show that "$P$ implies $Q$"? Assume that $P$ is ...
2
votes
1answer
57 views

Propositional Calculus: An algorithm to determine whether a finite sequence belongs to $\mathcal{L_0}$

Let $\mathcal{L_0}$ be the smallest set $L$ of finite sequences of $\textit{logical symbols}= \{(\enspace)\enspace\neg\}$ and $\textit{propositional symbols}=\{A_n|n\in\mathbb{N}\}$ for $n \in ...
1
vote
1answer
32 views

Representing sentences as propositional logic statements

I'm currently studying logical propositions through distance education for a college course and I'd like some assistance and critique on translating simple sentences into propositional logic ...
0
votes
1answer
31 views

Finding proportions…

kindly accept my apology in advance as i am not good in mathematics and this post might be trivial for some of the forum members. Consider I have $100 and I want to distribute among three poor people ...
2
votes
1answer
33 views

Propositional logic and distributive law

I am having trouble trying to understand how this question passes from this point $$ ( ( p\vee q )\wedge (p \vee \neg r ) \wedge (\neg q \vee \neg r ) ) \vee ( \neg p \vee r ) $$ to this $$ ...
1
vote
1answer
28 views

Logic Inference, Steps & Reasons

Going from ¬(¬q → s) to ¬q ∧ ¬s, I am confused. Is this using expression for implication, double negation and DeMorgan's? The following is what I thought: I thought first in terms of the rule that q ...
2
votes
3answers
192 views

Deducing $(\lnot B) \to A$ from $\lnot A \to B$ using Hilbert deductive system

As the title says, I've been trying to prove this: $(\lnot A \to B) \vdash (\lnot B) \to A)$ but unfortunately keep winding up with crazy long steps and then I have no idea where to go. The only ...
0
votes
1answer
50 views

On the truth-value of implication connective

As I have come to understand, in classical logic, the implication statement turns out to be true if the premise is false. It seems to be a little counter-intuitive, as it seems to me that the truth ...
1
vote
1answer
70 views

How to prove (¬((p→q) → ¬(q→r))) → (p→r) using Lukasiewicz's axioms and MP?

I need a proof for (¬((p→q) → ¬(q→r))) → (p→r) (which is equivalent to (p→q)→((q→r)→(p→r))) using the three axioms and MP: Axiom 1: $A \to (B \to A)$. Axiom 2: $(A \to (B \to C)) \to ((A \to B) \to ...
2
votes
3answers
55 views

Propositional calculus algebra

Can somebody explain me the following equivalence in propositional algebra(by the use of the laws of algebra): $$\lnot(p \lor q) \lor (\lnot p \land q) \equiv \lnot p$$ I get stuck after $$\lnot(p ...
3
votes
1answer
59 views

Propositional Logic: Conditions for a sequence to be an element of $\mathcal{L_0}$

Let $\mathcal{L_0}$ be the smallest set $L$ of finite sequences of $\textit{logical symbols}= \{(\enspace)\enspace\neg\}$ and $\textit{propositional symbols}=\{A_n|n\in\mathbb{N}\}$ for $n \in ...
2
votes
2answers
92 views

Biconditional Introduction in natural deduction

I'm working on a first-order logic question and I'm a little stuck as to what I should be assuming in my first subproof (this is always my problem). I'm supposed to prove this biconditional argument ...
1
vote
2answers
70 views

Propositional Logic: For which natural numbers $n$ are there elements of $\mathcal{L_0}$ of length $n$?

Let $\mathcal{L_0}$ be the smallest set $L$ of finite sequences of $\textit{logical symbols}= \{(\enspace)\enspace\neg\}$ and $\textit{propositional symbols}=\{A_n|n\in\mathbb{N}\}$ for $n \in ...
3
votes
4answers
86 views

How to negate an implication in English?

How to negate this proposition: "If $xy$ is irrational then either $x$ is irrational or $y$ is irrational. " Because the negation of $p\Rightarrow q$ is $p \wedge \text{not } q$. If I translate this ...
0
votes
1answer
40 views

Is the Cardinality of the Set of Contingent Propositions the Same as the Cardinality of the Set of Tautologies?

Is the Cardinality of the Set of Contingent Propositions the Same as the Cardinality of the Set of Tautologies? By a "contingent proposition" I mean a proposition which is neither a tautology or ...
0
votes
2answers
77 views

Proofs in Propositional Calculus

$X \simeq Y$ reads as $X$ is equivalent to $Y$ If $X \simeq Y$, iff $X \leftrightarrow Y$ is a tautology. Now given $X_1 \simeq X_2$, how do I prove, $\tilde X_1 \simeq \tilde X_2$ $X_1 \cap ...
2
votes
3answers
118 views

natural deduction proof

Need help with the steps for natural deduction: P1. $(A \rightarrow B) \rightarrow (C \rightarrow A)$ P2. $A \wedge (C \leftrightarrow B)$ P3. $(A \lor C) \to (A \to B)$ ...
0
votes
1answer
231 views

Which of these sentences are propositions? What are the truth values of those that are propositions?

Which of these sentences are propositions? What are the truth values of those that are propositions? a) Boston is the capital of Massachusetts. b) Miami is the capital of Florida. c) 2 + 3 = 5. d) 5 + ...
2
votes
3answers
71 views

Difficulty understanding why $ P \implies Q$ is equivalent to P only if Q.

I have difficulties understanding why $ P \implies Q$ is equivalent to P only if Q. I do understand that in the statement "P only if Q", it means if $ \lnot Q \implies \lnot P$". Regarding this ...
-2
votes
1answer
127 views

State the value of x after the statement [closed]

State the value of x after the statement if P(x) then x := 1 is executed, where P(x) is the statement “x > 1,” if the value of x when this statement is reached is x = 0. x = 1. x = 2. this answer ...
2
votes
1answer
57 views

Show that: $\sum \models p_1 \lor p_2 \lor … \lor p_n$ for some $n\in \mathbb{N}$

The question states: Suppose that, for each $i \in \mathbb{N}$, $p_i$ is a propositional variable. Let $\sum$ be a set of sentences of the propositional calculus . Suppose that all truth assignments ...
2
votes
1answer
48 views

Show that are logically equivalent [duplicate]

Show that are logically equivalent (without truth table) (p → r) ∧ (q → r) and (p ∨ q) → r My solution: ...
0
votes
1answer
23 views

Propositional Calculus - Validity

I have the following question: I have drawn a truth table below: From the table I believe that the answer is not C. However I am not sure whether the premise is incorrectly defined as the ...
1
vote
2answers
62 views

Determine whether {¬q∧(p→q)}→¬p is tautology

Determine whether $\{¬q∧(p→q)\}→¬p$ is tautology . this my solution : \begin{align} \{¬q∧(p→q)\}→¬p & ≡¬\{¬q∧(¬p∨q)\}∨¬p \\ &≡q∨(p∧¬q)∨¬p≡(q∨p)∧(¬q∨¬p) \\ &≡(q∨¬q)∧(p∨¬p) ≡T∧ T \\ ...