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

For any set of formulas in propositional logic, there is an equivalent and independent set

A set of formulas is independent if no proper subset is logically equivalent to it. Note that this exercise appears in Enderton 1.2 10(c) and is marked as star.
1
vote
1answer
20 views

Distribute ANDs over ORs in this sentence

Can someone explain how we turn the sentence $$[\neg C(x,y)]\vee [\neg A(x) \vee B(x)\wedge C(x,y)]$$ into conjunctive normal form by distributing the ANDs over the ORs? It's confusing me because ...
1
vote
3answers
39 views

Reverse of Deduction Theorem

Why is it "easy to see" that if $S \vdash (A\to B)$ then $S \cup\{A\} \vdash B$?
0
votes
0answers
19 views

Justify each step in the following proof of Proposition 3.9 (a). I like to know if I'm in the right track and I'm also missing a few of them

Proposition 3.9(a): If a ray r emanating from an exterior point of triangle ABC intersects side AB at a point between A and B, then r also intersects side AC or side BC. proof. (a) Let r= array XD ...
5
votes
1answer
31 views

FOL and Conjuctive Normal Form Conversion

I see the CNF from following firs order logic: $ \forall x [ \forall y [ \neg A(y) \vee B(x,y) \Rightarrow [ \neg \forall y B(y,x) ] ] $ is equivalent to : $ (A(f(x)) \vee \neg B(g(x),x)) \wedge ...
1
vote
1answer
22 views

propositional-calculus/logic riddle

Two physicists, A and B, and a logician C, are wearing hats, which they know are either black or white but not all white. A can see the hats of B and C; B can see the hats of A and C; C is blind. Each ...
1
vote
1answer
35 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
18 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
25 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
40 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
55 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
25 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
0answers
18 views

Translating sentences into sentential calculus [on hold]

William Shakespeare was William Shakespeare if and only if he wasn’t Francis Bacon.
0
votes
1answer
46 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 ...
3
votes
2answers
203 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
25 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
0answers
38 views

Non-equivalent k-DNF formula [on hold]

Let's define k-DNF. So ours formula is k-DNF, where $k \in \mathbb{N}$ if $$\bigvee^{n}_{i=1} \left(\bigwedge^{k}_{j=1} l_{ij} \right)$$ for some logic variables $l_{ij}$. ($n$ is arbitrary large, ...
0
votes
2answers
32 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
25 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
45 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
36 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
60 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
34 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
0answers
33 views

First-Order Logic: Examples of infinite $\mathcal{L}_A$ structures with certain properties [closed]

Let $A=\{F_1\}$ be the alphabet with one unary function symbol. Give an example of different infinite $\mathcal{L}_A$ structures $\mathcal{m} = (M,I)$ with the following properties: (a) $\mathcal{m}$ ...
0
votes
3answers
67 views
2
votes
2answers
56 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.
-1
votes
0answers
16 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
28 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
83 views

Discrete mathematics Logic Proof

I'm stuck with these problems... ...
0
votes
1answer
45 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
30 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
66 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
45 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
31 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
57 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
52 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
24 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
28 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 ...
-1
votes
0answers
32 views

Writing every propositional formula in terms of three expressions

Consider the expressions $\leftrightarrow$, $\top$, and $\bot$. Is it necessarily true that every propositional formula can be written only in terms of these three symbols?
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
25 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
133 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
39 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
59 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
47 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
54 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
62 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
66 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
72 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 ...