All Questions
69
questions
1
vote
2
answers
64
views
XOR sum of array
When you are given an array of even number of elements:
[$a_1$ $a_2$ $a_3$ ….. $a_n$] ($n$ is even)
Assume the $a_i$ are not all zero
Let $S$ = the XOR sum of all these original elements
You will ...
1
vote
1
answer
39
views
Constructing Truth Tables for Formulas with Variable Valuations
I was solving a problem from old exams and got stuck here. I'd appreciate the help.
We have the three variables p, q, and r. There are 8 valuations of the variables. If F is a propositional logic ...
-1
votes
1
answer
59
views
Hoare Logic: If-statement
Can someone explain the first assignment and implied? We prove bottom to up and I don't follor after the $(1=x+1)$ if-Statement. This is what my book says about the assignment rule:
, if we wish to ...
3
votes
1
answer
50
views
Finding a bound for existential quantification
Let $\Sigma$ be an arbitrary alphabet, $\mathcal{P}$ denote the set of all prime numbers, and $\omega := \mathbb{N} \cup \{0\}$ Take the following set.
$$
L = \left\{ (x, \alpha, \beta) \in \omega \...
0
votes
0
answers
18
views
Do we try to prevent cycles in temporal logic (CTL)?
When looking at the formulas for the rules in CTL, it is said that we save the states we have already been in a in list/ set. Does that mean that we are trying to preven endless loops?
For example ...
0
votes
1
answer
95
views
Natural deduction with $(A→B)→C, A∧B ⊢C$
$(A → B) → C, A ∧ B \vdash C$
1.$\hspace{1cm}(A → B) → C \hspace{1cm}$premise
2.$\hspace{1cm}A ∧ B \hspace{2.5cm}$ premise
$\hspace{2cm}$ 3. $\hspace{1cm} A \to B \hspace{1cm}$ Assumption
$\hspace{2cm}...
0
votes
0
answers
74
views
Is this natural deduction proof of $\exists x \neg Px \vdash \neg \forall x Px$ correct?
When it comes to proofs there is no way to tell whether I have done correct or not. In the solution they did in another way which makes me wonder if this correct? For future question, how can I verify ...
0
votes
2
answers
232
views
How to prove with natural deduction?
Given this question, I tried solving in the first picture as you can see, but I didn't know how to continue and the second image is the right way to solve it. My question is have I done right so far? ...
0
votes
0
answers
54
views
Propositional logic: Natural deduction
Is the first solution valid? If not, can someone explain to me why the first solution is not valid but the second one is? Both claim that p and not p is true though?
$\lnot p \to p \vdash p$
$1 \...
6
votes
5
answers
420
views
Need an intuitive example for how "P is necessary for Q" means "Q$\implies$P"?
I am confused about how "P is necessary for Q" means "Q$\implies$P" (source: Kenneth Rosen DMGT).
Intuitively, I interpret "P is necessary for Q" as "for Q to happen,...
-2
votes
2
answers
152
views
Logic equivalence question
I have a question about discrete mathematics question that I have been struggling to solve. Here is the question:
Each of the two rooms (room I and room II) contains either a lady or a tiger. If a ...
0
votes
1
answer
51
views
Formal proof for a set of closed logical sentences.
I am currently taking a course in logic for computer science and reading a book by M. R. A. Huth and M. D. Ryan, Logic in Computer Science. I came across an exercise where I understand but need help ...
1
vote
2
answers
130
views
How to formalize and prove a reasoning as propositional logic?
If both E and H are at a lecture, then A won't be there. If E is at the lecture, then H will also be there. If A is not at the lecture, then E will be there. Thus, either E but not A is at the lecture,...
1
vote
4
answers
477
views
How to show that $p∨q, q∨r, p\to ¬r ⊢ q$?
How to prove $p∨q, q∨r, p\to ¬r ⊢ q$ using natural deduction?
I don't really know how to go about it since I have 2 or statements, but here is my try.
$p∨q$ premise
$q∨r$ premise
$...
4
votes
0
answers
79
views
Prove that $A^{c}\subseteq B\cap C^{c}$ iff $(A\cup B)\cap(A\cup C^{c}) = U$ [closed]
Let $A$ and $B$ be subsets of the universal set $U$. Prove that
$$A^{c}\subseteq B\cap C^{c} \Longleftrightarrow (A\cup B)\cap(A\cup C^{c}) = U$$
We haven't learned any laws surrounding subsets in ...