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)

0
votes
1answer
53 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
217 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
29 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
37 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
26 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
47 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
37 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
63 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
36 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
38 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
75 views
2
votes
2answers
74 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
27 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 ...
3
votes
0answers
34 views

Let $\Gamma$ be a set of formulas and $\phi$. Show that $\Gamma \cup \{\neg \phi\}$ is satisfiable if and only if $\Gamma\not \models \phi$

This seemed pretty obvious but I wanted to see if my proof made sense: Proof: $(\Rightarrow)$ To derive for a contradiction, suppose that: $\Gamma \models \phi$. That means for all truth assignments ...
1
vote
1answer
98 views

Discrete mathematics Logic Proof

I'm stuck with these problems... ...
0
votes
1answer
48 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
38 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
74 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
50 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
35 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?
1
vote
4answers
60 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
56 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
28 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
29 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
31 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
27 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
168 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
44 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
66 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
48 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
57 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
88 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
69 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
78 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
0answers
23 views

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 contradiction. Or in other words, there exists at least one valuation of the variables such that the formula ...
0
votes
2answers
76 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
106 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
93 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
64 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
78 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
55 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
45 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
21 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
47 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 \\ ...
1
vote
1answer
25 views

Propositional Calculus - Validity Question

I have the following question: And I have drawn up the truth table below: My question is I see there is one truth value that both the premise and conclusion have in common, but does that mean ...
0
votes
1answer
85 views

Can ECpqANpq get proved in intuitionistic logic?

I use Lukasiewicz/Polish notation. Given intuitionistic logic with the optional axioms for equivalence and negation given in the Wikipedia, can ECpqANpq or in other notation ...
2
votes
2answers
50 views

Show that $(\phi \rightarrow \psi), (\phi \rightarrow \neg \psi) \vdash \neg \phi$

I need to show that $(\phi \rightarrow \psi), (\phi \rightarrow \neg \psi) \vdash \neg \phi$ using the axioms: For any formula $\psi,\theta, \phi$ $$ 1.:(\psi \rightarrow (\theta \rightarrow \psi))$$ ...
2
votes
1answer
49 views

How to show $\vdash (\neg\neg p \rightarrow p)$.

Given these axioms: where $\phi, \psi, \theta$ are formulas $$ 1.:(\psi \rightarrow (\theta \rightarrow \psi))$$ $$ 2.: ((\neg \psi \rightarrow \neg \theta) \rightarrow (\theta \rightarrow \psi))$$ ...
0
votes
1answer
54 views

If no interpretations satisfy a set of formulae U, is it possible for $U\models A$?

Note: '$ \models$' denotes logical consequence, defined as If $U \models A$, then $A$ is a logical consequence of $U$, if and only if every interpretation that satisfies U also satisfies $A$, ...
-1
votes
2answers
61 views

Natural deduction: given premises, conclude $M \lor E$. [closed]

I need to prove that the following argument is valid using Natural Deduction: 1.  $[\lnot (B \lor \lnot I) \rightarrow (\lnot L \land J)]$ 2.  $[\lnot L \rightarrow (M \land B)]$ 3.  $\lnot (B ...